PHP.SU

Программирование на PHP, MySQL и другие веб-технологии

PHP.SU Портал

Главная

Помощь

Поиск

Поиск Яндекс Вакансии

Пользователи

Здравствуйте, Гость

( Вход · Регистрация · Правила форума )

Забыли пароль?

Вопрос к программистам

Форумы портала PHP.SU » Разное » Прочее (Модераторы: RomAndry, ALEN, Строитель)

Страниц (9): « 1 2 3 4 5 [6] 7 8 9 »

Описание: Комбинаторика, алгоритмы и прочее - в программном коде

Поиск в теме | Версия для печати

soffrick	Отправлено: 25 Июля, 2013 - 14:10:04
Посетитель Покинул форум Сообщений всего: 379 Дата рег-ции: Май 2012 Откуда: Россия, Москва Помог: 17 раз(а)	VenZell PHP: скопировать код в буфер обмена return empty($clean_str) ? true : false; зачем так? ----- Правильный вопрос - уже половина правильного ответа! p.s. индусы повсюду, будьте осторожны!

EuGen	Отправлено: 25 Июля, 2013 - 14:11:40
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	Одна из классических задач по упаковке. Существует некоторый контейнер с максимальной грузоподъёмностью W. Существует N грузов e_i. Каждый груз имеет две характеристики - вес w_i и стоимость v_i (1 < i <= N). Считаем, что геометрические особенности грузов и контейнера несущественны, и единственная характеристика - это вес. Набор предметов может быть помещён в контейнер, если суммарный вес набора не превышает W. Каждый предмет можно выбрать только один раз. Дан входной набор данных для грузов e_i, который представляет собой массив из пар значений - веса предмета w_i и стоимости предмета v_i - пусть для определённости это будет реализовано как ассоциативный массив с ключами weight и value. Дано также число W. Все значения весов и стоимостей, а также грузоподъёмность контейнера W - являются положительными целыми числами. Для определённости также считаем, что 0 < W <=100 и 0 < w_i <=100 (то есть все веса предметов, а также грузоподъёмность контейнера больше нуля и меньше либо равны 100). Далее, количество грузов N тоже положительно (не может быть пустого набора) и не превышает 1E5 Требуется - по данному набору предметов {e_i} и числу W найти число V, которое является максимальной суммарной стоимостью предметов, которые удалось поместить в контейнер (сумма весов этих предметов не превышает W) - то есть написать функцию getMaxValue, принимающую два параметра - набор грузов и величину W, и возвращающую единственное целое число V - максимально достижимую стоимость набора предметов, которые можно поместить в контейнер. Пример: PHP: скопировать код в буфер обмена $rgData = [ ['weight'=>2, 'value'=>4], ['weight'=>5, 'value'=>7], ['weight'=>1, 'value'=>3], ['weight'=>3, 'value'=>4] ]; $iMaxWeight = 5; var_dump(getMaxValue($rgData, $iMaxWeight)); //8 вариант (Отобразить) CODE (php): скопировать код в буфер обмена function getMaxValue($rgItems, $iMaxWeight) { $rgMaxs = []; $rgMaxs[0] = array_fill(0, $iMaxWeight+1, 0); for($i=1; $i<=count($rgItems); $i++) { for($j=0; $j<=$iMaxWeight; $j++) { $rgMaxs[$i][$j] = $j>=$rgItems[$i-1]['weight']?max([$rgMaxs[$i-1][$j], $rgMaxs[$i-1][$j-$rgItems[$i-1]['weight']]+$rgItems[$i-1]['value']]):$rgMaxs[$i-1][$j]; } } return $rgMaxs[count($rgItems)][$iMaxWeight]; } ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

VenZell	Отправлено: 25 Июля, 2013 - 14:17:31
Частый гость Покинул форум Сообщений всего: 237 Дата рег-ции: Июнь 2013 Помог: 12 раз(а)	soffrick, парные скобки из строки удаляются, остаются только те, что остались без пары. Соответственно, если выходная строка пуста - все скобки правильно закрыты. Отсюда такое условие. upd: понял, где косяк. (Отредактировано автором: 25 Июля, 2013 - 14:30:06)

Мелкий	Отправлено: 16 Августа, 2013 - 11:54:38
Активный участник Покинул форум Сообщений всего: 11926 Дата рег-ции: Июль 2009 Откуда: Россия, Санкт-Петербург Помог: 618 раз(а)	По задачке со скобками вариант. Как говорится, не делайте так, но так сделать можно: Спойлер (Отобразить) PHP: скопировать код в буфер обмена function checkBrackets($sData) { $sRegexp = '#^((?:$(?1)$\|\[(?1)\]\|\{(?1)\}\|[^()\[\]\{\}]++)+)$#'; return preg_match($sRegexp, $sData); } assert('checkBrackets("(()()([][])[])")==true'); assert('checkBrackets("abc([dy][dx]Fz)")==true'); assert('checkBrackets("")==true'); assert('checkBrackets("()[]")==true'); assert('checkBrackets("foo()")==true'); assert('checkBrackets("foo(")==false'); assert('checkBrackets("pqr[Gdz)/(Hdx]")==false'); //test pass ----- PostgreSQL DBA

EuGen	Отправлено: 16 Августа, 2013 - 11:57:51
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	Мелкий Сделать можно. Плохо масштабируется на другое число скобок (и/или другие пары), разумеется. Вообще обработать строку регулярным выражением до работы проверки корректности расстановки скобок - идея хорошая, поскольку позволяет сократить объем работы, вероятно, на порядки. ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

nerv	Отправлено: 17 Августа, 2013 - 21:16:10
Посетитель Покинул форум Сообщений всего: 407 Дата рег-ции: Февр. 2013 Откуда: Россия Помог: 9 раз(а)	вариант со скобками (не самый оптимальный) CODE (javascript): скопировать код в буфер обмена function test( text ) { var hash = { '(': 1, '[': 1, '{': 1, '}': -1, ']': -1, ')': -1 }; var position = { '(': 0, '[': 1, '{': 2, '}': 2, ']': 1, ')': 0 }; var index = text.length; var result = [ 0, 0, 0 ]; while( index-- ) { var chr = text[ index ]; result[ position[ chr ] ] += hash[ chr ]; if ( result[ position[ chr ] ] > 0 ) { return false; } } return !result.filter(function( item ) { return item !== 0; }).length; } console.log( 'abc([dy][dx]Fz)', test( 'abc([dy][dx]Fz)' ) ); console.log( 'pqr[Gdz)/(Hdx]', test( 'pqr[Gdz)/(Hdx]' ) ); console.log( 'foo', test( 'foo' ) ); console.log( 'foo()', test( 'foo()' ) ); console.log( ']', test( ']' ) ); console.log( '(){[]}', test( '(){[]}' ) ); ----- Чебурашка стал символом олимпийских игр. А чего достиг ты? Тишина - самый громкий звук

EuGen	Отправлено: 25 Сентября, 2013 - 16:35:02
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	Поясните, почему в PHP следующие две программы дадут одинаковый результат (3) : PHP: скопировать код в буфер обмена $x = 1; $y = $x + $x++; var_dump($y); и PHP: скопировать код в буфер обмена $x = 1; $y = $x + $x + $x++; var_dump($y); hint0 (Отобразить) Помочь понять это (а, может, наоборот, запутать) вам может следующая конструкция: CODE (php): скопировать код в буфер обмена $x = 1; @ $y = $x + $x++; var_dump($y); // int(2) hint1 (Отобразить) На самом деле, я не ожидаю, что кто-либо даст достаточно точный ответ, но мне интересен ход мыслей. Вопрос можно отнести к весьма сложным, поскольку для ответа на него нужны специальные знания. ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

LIME	Отправлено: 25 Сентября, 2013 - 16:55:51
Активный участник Покинул форум Сообщений всего: 10732 Дата рег-ции: Нояб. 2010 Помог: 322 раз(а)	мне кажется дело в отложенном копировании ?

EuGen	Отправлено: 25 Сентября, 2013 - 16:56:42
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	LIME пишет: мне кажется дело в отложенном копировании Нет. Далеко от истины - и не поясняет разницы при применении "@" (см. hint0 - впрочем, ответа нет ни в одном из hint) ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

SAD	Отправлено: 25 Сентября, 2013 - 16:57:31
Постоянный участник Покинул форум Сообщений всего: 2508 Дата рег-ции: Май 2009 Откуда: Днепропетровск, Украина Помог: 75 раз(а)	мозг бдыщь

imya	Отправлено: 25 Сентября, 2013 - 16:57:50
Участник Покинул форум Сообщений всего: 1472 Дата рег-ции: Сент. 2012 Откуда: Запорожье, Украина Помог: 19 раз(а)	EuGen , из-за посткремента ? ----- PHP: скопировать код в буфер обмена do {box != cat;} while (cat != box); Когда нормальный человек, уезжая из дома одевает на жену пояс верности, веб-дизайнер ставит на нее счетчик...

EuGen	Отправлено: 25 Сентября, 2013 - 16:59:53
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	imya пишет: из-за посткремента ? Из-за постинкремента что? ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

imya	Отправлено: 25 Сентября, 2013 - 17:03:36
Участник Покинул форум Сообщений всего: 1472 Дата рег-ции: Сент. 2012 Откуда: Запорожье, Украина Помог: 19 раз(а)	EuGen пишет: Из-за постинкремента что? Получается одинаковый результат. Ведь если написать ++$x(прекремент) , то произойдёт операция $х = $х+1, а потом уже остальные действия. В случае же с $x++(посткремент), вначале выполнятся действия, предшествующие операции, а после уже $х=$х+1. Или я неправ? ----- PHP: скопировать код в буфер обмена do {box != cat;} while (cat != box); Когда нормальный человек, уезжая из дома одевает на жену пояс верности, веб-дизайнер ставит на нее счетчик...

LIME	Отправлено: 25 Сентября, 2013 - 17:05:30
Активный участник Покинул форум Сообщений всего: 10732 Дата рег-ции: Нояб. 2010 Помог: 322 раз(а)	постинкремент создает временную переменную а преинкремент увеличивает настоящую но как бы и что?))

EuGen	Отправлено: 25 Сентября, 2013 - 17:05:42
Профессионал Покинул форум Сообщений всего: 9095 Дата рег-ции: Июнь 2007 Откуда: Berlin Помог: 707 раз(а)	imya пишет: Или я неправ? Нет. Это не поясняет ничего - то есть вопрос остаётся в силе - вне зависимости от того, как работает постинкремент, нужно понять, почему в первом случае слагаемых два (и один постинкремент), а во втором - три (и снова постинкремент один и на той же позиции), но результат одинаковый. И, как бонус - почему при применении "@" в первом случае результат меняется (и почему на 2) ----- Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

Поиск в теме | Версия для печати

Страниц (9): « 1 2 3 4 5 [6] 7 8 9 »

Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)

« Прочее »

Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.