Персональный сайт

Задача 1 – Лишние скобки

Необходимо написать функцию, которая из вводимой строки, содержащей запись арифметического выражения, удаляет лишние скобки. Скобки считаются лишними, если их отсутствие не влияет на значение выражения, либо их использование недопустимо. Выражение содержит только переменные, состоящие из латинских букв, знаки четырех операций (+, –, * и /) и круглые скобки.

Результат работы программы

Исходное выражение: ((a+b))*(d-f)
Постфиксная форма: ab+df-*
Инфиксная форма: (a+b)*(d-f)

Пример PHP–кода:

class infpref{ var $operandChars = array('/', '*', '-', '+'); var $operandPriority = array(6, 6, 5, 5); var $stack = array(); function getOperandPriority( $c ){ $index = array_search($c , $this->operandChars); return $this->operandPriority[ $index ]; } function getElementPriority( $el ){ return $el[1]; } function postfixToInfix( $inString ){ $arrChars = str_split( $inString ); $i = 0; $ls = sizeof( $arrChars ); while ( $i < $ls ){ if (in_array($arrChars[ $i ], $this->operandChars)){ $el1 = array_pop( $this->stack ); $el2 = array_pop( $this->stack ); $op = (int)$this->getOperandPriority( $arrChars[ $i ] ); $ep1 = (int)$this->getElementPriority( $el1 ); $ep2 = (int)$this->getElementPriority( $el2 ); if (( $ep1 != 0) && ( $ep1 < $op )){ $valEl1 = '(' . $el1[0] . ')'; } else { $valEl1 = $el1[0]; } if (( $ep2 != 0) && ( $ep2 < $op )){ $valEl2 = '(' . $el2[0] . ')'; } else { $valEl2 = $el2[0]; } $tmpEl = array( $valEl2 . $arrChars[ $i ] . $valEl1, $op ); array_push( $this->stack, $tmpEl ); $i++; } else { while (( !in_array( $arrChars[ $i ], $this->operandChars )) && ( $i < $ls )){ array_push( $this->stack, array( $arrChars[ $i ], 0 )); $i++; } } } $result = array_pop( $this->stack ); return $result[0]; } function stackNotOp(){ foreach( $this->stack as $el){ if (in_array($el[0], $this->operandChars)){ return true; } } return false; } function stackTopEl(){ $a = array_reverse($this->stack); if ( $a[0][0] == ')'){ return true; } else { return false; } } function getTopOperandPriority(){ $a = array_reverse($this->stack); foreach ($a as $el){ if (in_array( $el[0], $this->operandChars )){ return $this->getOperandPriority( $el[0] ); } } return 0; } function stackToStr2c( $elChar ){ $strTmp = ''; $op = (int)$this->getOperandPriority( $elChar ); do { $el = array_pop( $this->stack ); if (in_array( $el[0], $this->operandChars )){ $opn = (int)$this->getOperandPriority( $el[0] ); } else { if ($el[0] != '('){ $strTmp .= $el[0]; } } } while (( $op <= $opn ) && ($el[0] != '(')); array_push( $this->stack, array( $elChar, $this->getOperandPriority($elChar) )); return $strTmp; } function stackToStr4(){ $strTmp = ''; do { $el = array_pop( $this->stack ); if ($el[0] != '('){ $strTmp .= $el[0]; } } while ($el[0] == '('); return $strTmp; } function infixToPostfix( $inString ){ $arrChars = str_split( $inString ); $arrChars = preg_grep('/[a-zA-Z\*\+-\/()]/', $arrChars); $max = sizeof( $arrChars ); $str = ''; for($i=0; $i<$max; $i++){ if (in_array( $arrChars[$i], $this->operandChars )){ if (($this->stackNotOp()) || ($this->stackTopEl() == '(')){ array_push( $this->stack, array( $arrChars[ $i ], $this->getOperandPriority( $arrChars[ $i ] ))); } if ( $this->getOperandPriority( $arrChars[ $i ] ) > $this->getTopOperandPriority() ){ array_push( $this->stack, array( $arrChars[ $i ], $this->getOperandPriority( $arrChars[ $i ] ))); } else { $str .= $this->stackToStr2c( $arrChars[ $i ] ); } } else { if (( $arrChars[ $i ] != '(' ) && ( $arrChars[ $i ] != ')' )){ $str .= $arrChars[ $i ]; } } if ( $arrChars[ $i ] == '(' ){ array_push( $this->stack, array('(', 0)); } if ( $arrChars[ $i ] == ')' ){ $str .= $this->stackToStr4(); } } while ($this->stack){ $tmp = array_pop( $this->stack ); if ($tmp[0] != '('){ $str .= $tmp[0]; } } return $str; } }

Задача 2 – Анаграммы

Во входном файле (или строковом параметре функции) содержится строка длиной не более 255 символов, в которой через один или несколько пробелов следуют слова. Найти все группы анаграмм (слов, составленных из одних и тех же символов) в этой строке и вывести на устройство вывода (или в файл) их каждую с новой строки, все слова должны идти через пробел в порядке, в котором они встречаются в строке. При этом допускается выводить одинаковые слова в одной строке анаграмм. Слова состоящие из разного количества одинаковых букв анаграммами не являются.

Пример:

Входная строка:
    «123 456 231 546 231 312 4556»
Результат:
	123 231 231 312
	456 546
	4556

Результат работы программы

123 456 231 546 231 312 4556
123 231 231 312
456 546
4556

Пример PHP–кода:

$s = '123 456 231 546 231 312 4556'; $arr = explode( ' ', $s ); // сначала переводим строку в массив слов $max = sizeof( $arr ); $rez = array(); for ($i=0; $i<$max; $i++){ // сортируем каждое слово по возрастанию кода символов $arrS = str_split( $arr[ $i ]); sort( $arrS ); $rez[ $i ] = implode($arrS); } $r = array_unique( $rez ); // удаляем дубликаты echo $s . '<br>'; foreach ($r as $ritem){ // формируем строки анаграмм $cur = $ritem; for ($i=0; $i<$max; $i++){ if ( $rez[ $i ] == $cur ){ echo $arr[ $i ] . ' '; } } echo '<br>'; }

Задача 3 – Драконова ломаная

Драконова ломаная N-го порядка строится посредством сворачивания N раз пополам полоски бумаги в одном направлении и от одной точки, с последующим разворачиванием каждого угла в 90 градусов. Проекция такой полоски на плоскость и будет искомой ломаной. (На рисунке справа показан порядок изгибания полоски для получения ломаной 1 и 2-го порядка, на рисунке слева полоски отражающие ломаные 3 и 4-го порядка). Требуется реализовать алгоритм построения ломаной N-го порядка в виде процедуры, создающей и заполняющей булевыми значениями (0/1) одномерный массив определенной размерности, содержащий направления поворотов ломаной. (На рисунке слева приведены ломаные 1,2 и 3 порядков и соответствующие им результирующие массивы. Стартовая точка ломаных помечена. Поворот по часовой стрелке кодируется 0 (нулем), поворот против часовой стрелки кодируется 1 (единицей).

Для решения задач допускается использование произвольного языка программирования, позволяющего объявлять линейные массивы и адресовать элементы массива по индексу. Пример: А=Массив[Х]; В=А[i]; А[j] = NOT А[i]; Для лучшего осознания задачи рекомендуется использовать реквизит (полоску бумаги), например оторвав ее по линии от верхней части страницы.

Результат работы программы

Глубина:
Не рекурсивный ( с массивом )
Рекурсивный ( без массива )

Использованы два алгоритма:

Не рекурсивный. Как в задании - формируем массив поворотов а потом по нему рисуем линию.
Рекурсивный. Не формирует массив (можно дополнительно вызвать функцию формирования массива), а сразу рисует линию. Данный алгоритм нашёл в интернете на Delphi и переделал не много изменив под JavaScript и HTML5.

Задача 4 – Запрос

В базе данных имеются две похожих таблицы с данными (таб_А и таб_Б) представленных ниже:

Таблица таб_А
ТипЗаявки	Ссылка	Состояние	Дата
Внутр.Задача	Внутренняя задача 000000043	Назначена	22.01.2013 11:24:12
Внутр.Задача	Внутренняя задача 000000043	Принята	24.01.2013 17:35:22
Внутр.Задача	Внутренняя задача 000000043	Завершена	24.01.2013 17:35:29
Внутр.Задача	Внутренняя задача 000000043	Одобрена	27.01.2013 8:59:47
Внутр.Задача	Внутренняя задача 000000056	Назначена	28.11.2012 12:16:52
Внутр.Задача	Внутренняя задача 000000056	Принята	28.11.2012 12:29:03
Внутр.Задача	Внутренняя задача 000000056	Завершена	28.11.2012 12:29:06
Внутр.Задача	Внутренняя задача 000000056	Одобрена	28.11.2012 12:30:12

Таблица таб_Б
ТипЗаявки	Ссылка	Состояние	Дата
ЗаявкаИТ	Заявка ИТ 000000018	Назначена	10.01.2013 18:18:39
ЗаявкаИТ	Заявка ИТ 000000398	Назначена	11.02.2013 9:39:58
ЗаявкаИТ	Заявка ИТ 000000398	Принята	11.02.2013 14:34:03
ЗаявкаИТ	Заявка ИТ 000000447	Назначена	14.02.2013 17:20:46
ЗаявкаИТ	Заявка ИТ 000000474	Назначена	15.02.2013 10:32:52
ЗаявкаИТ	Заявка ИТ 000000474	Принята	17.02.2013 10:32:11
ЗаявкаИТ	Заявка ИТ 000000474	Завершена	17.02.2013 12:26:04
ЗаявкаИТ	Заявка ИТ 000000475	Назначена	16.02.2013 17:14:30
ЗаявкаИТ	Заявка ИТ 000000475	Назначена	16.02.2013 18:14:30
ЗаявкаИТ	Заявка ИТ 000000475	Принята	17.02.2013 10:41:48
ЗаявкаИТ	Заявка ИТ 000000475	Завершена	17.02.2013 12:26:08

Необходимо составить запрос, возращаюший набор данных в виде:

ТипЗаявки	Ссылка	Назначено_дата	Завершена_дата
Внутр.Задача	Внутренняя задача 000000043	22.01.2013 11:24:12	24.01.2013 17:35:29
Внутр.Задача	Внутренняя задача 000000056	28.11.2012 12:16:52	28.11.2012 12:29:06
ЗаявкаИТ	Заявка ИТ 000000018	10.01.2013 18:18:39
ЗаявкаИТ	Заявка ИТ 000000398	11.02.2013 9:39:58
ЗаявкаИТ	Заявка ИТ 000000447	14.02.2013 17:20:46
ЗаявкаИТ	Заявка ИТ 000000474	15.02.2013 10:32:52	17.02.2013 12:26:04
ЗаявкаИТ	Заявка ИТ 000000475	16.02.2013 18:14:30	17.02.2013 12:26:08

Запрос к таблицам в синтаксисе MSSQL Server

SELECT a.tipZayavki as [ТипЗаявки],
       a.ssilka as [Ссылка],
       a.data as [Назначено_дата],
       b.data as [Завершена_дата] 
  FROM (
    SELECT tipZayavki,ssilka, MAX(data) as data FROM tab_A WHERE sostoyanie = 'Назначена'
      GROUP BY tipZayavki,ssilka
    ) a 
    LEFT JOIN (SELECT * FROM tab_A WHERE sostoyanie = 'Завершена') b ON (a.ssilka = b.ssilka)
UNION
SELECT a.tipZayavki as [ТипЗаявки],
       a.ssilka as [Ссылка],
       a.data as [Назначено_дата],
       b.data as [Завершена_дата] 
  FROM (
    SELECT tipZayavki,ssilka, MAX(data) as data FROM tab_B WHERE sostoyanie = 'Назначена'
      GROUP BY tipZayavki,ssilka
    ) a 
    LEFT JOIN (SELECT * FROM tab_B WHERE sostoyanie = 'Завершена') b ON (a.ssilka = b.ssilka)

Результат работы программы

Для тестирования взят за основу MSSQL Server 2000. Сформируем таблицы и выполним на них запрос. Результаты представлены на рисунке ниже.

Далее, для наглядности, подключим наш запрос на вывод в каком-либо приложении. В нашем случае использована среда Delphi 7. Результат представлен на рисунке ниже.

Разработки