Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mmonline.ru/forum/read/7/53511/53511/
Дата изменения: Tue Apr 12 12:01:17 2016
Дата индексирования: Tue Apr 12 12:01:17 2016
Кодировка: Windows-1251
MMOnline | Форумы | Разное | Паскаль: Найти последовательность из 50 нулей и единиц в которой...

Паскаль: Найти последовательность из 50 нулей и единиц в которой...

Автор темы женек 
17.06.2007 15:06
Паскаль: Найти последовательность из 50 нулей и единиц в которой...
1. Найти последовательность из 50 нулей и единиц в которой никакой отрезок не повторяется три раза подряд. Напечатать нет, если такой последовательности не существует. Например нигде не должны встречаться такие отрезки как 000 или 101010 или 101101101

2. Из заданных N предметов выбрать такие, чтобы их суммарный вес был менее 30 кг, а стоимость наибольшей. Вывести суммарную стоимость выбранных предметов. Точнее - заданы два массива А[1..N], B[1..N]. Выбрать такие попарно различные числа I1, I2..IN, чтобы сумма A[I1], A[I2]:A[N]<30, а сумма B[I1], B[I2]:B[N]=max. Вывести только величину max. Можно предположить, что предметы уже расположены в порядке возрастания или убывания веса

НЕ знаю как решать напишите решение плиз
20.06.2007 14:53
Рекурсивный перебор, динам. программирование
Для задачи 1 можно попробовать рекурсивный перебор с отсечением лишних ветвей. На k-м уровне рекурсии перебирать значения a[k] и проверять на повторы. Достаточно проверять лишь цепочки, заканчивающиеся текущим элементом a[k]. Проверку удобно оформить как отдельную функцию с возвращаемым значением типа boolean и параметрами a, k.

Задачу 2 (задачу о рюкзаке) решают методом динамического программирования. Этот метод описан во многих учебниках (например, Кормен и др.) и методичках (гугль в помощь). Если хочется освоить метод ДП, а не просто найти готовое решение задачи о рюкзаке, то советую начать с простых упражнений:
http://www.olympiads.ru/sng/2/index.shtml
http://www.olympiads.ru/sng/3/index.shtml

01.07.2007 18:27
последовательность
А чего ж только 50?

program HelloWorld;

begin
writeln('10011001001100110110011001001100110110011001001100100110110011011001001100100110110011011001001100100110110010011011001011001001');
end.

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

Кликните здесь, чтобы войти