Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Внимание! Тест на интуицию :)

HRustBB © (2009-12-06 12:36:00)
Есть задача:
дано четыре числа 1 2 4 8. и есть число, назовем его Х, которое равно сумме двух, трех, четырех из этих чисел, либо какому нибудь одному из них. Дак вот, нужно определить из каких чисел из предложенного ряда сложенно Х. Да и кстати каждое из четырех указанных чисел участвует в сумме только один раз. Нужен алгоритм хотябы.

icWasya (2009-12-07 09:54:00) [1]
А если хочешь блеснуть эрудицией, то это называется задачей о рюкзаке, в которой исходные числа - произвольны.
И тогда она решается, как описано в [4].
А есть частный случай, когда в исходном наборе каждое последующее число больше суммы всех предыдущих.
Исходные числа 1,2,4,8 удовлетворяют этому условию
Тогда задача решается так:
1)Берём самое большое число
2) если Х больше этого числа, То это число входит в сумму; Уменьшаем Х на число.
3)выбрасываем число из набора.
4) Если чисел больше нет, то закончить, иначе повторить с 1)

Германн (2009-12-07 00:54:00) [2]

> Юрий Зотов © (07.12.09 00:33) [7]
>
> > Тест на интуицию
>
> :o)

Всё-таки да. На интуицию. :)

KilkennyCat (2009-12-07 00:44:00) [3]
на интуицию препода.

Юрий Зотов (2009-12-07 00:33:00) [4]
> Тест на интуицию

:o)

McSimm (2009-12-06 13:16:00) [5]

> AIK © (06.12.09 12:55) [4]

Число X, записанное в двоичном виде будет иметь в каждом разряде ноль или один. Позиции единиц соответствует искомым слагаемым в задаче.
Например X=12. Двоичная запись 1100 -> 1*8 + 1*4 + 0*2 + 0*1

Inovet (2009-12-06 13:04:00) [6]
> [4] AIK © (06.12.09 12:55)
> бегоем по циклу

А в нём shr 1 and 1

HRustBB (2009-12-06 12:55:00) [7]
ааа, comprento, спасибо досвиданья

AIK (2009-12-06 12:55:00) [8]
сперва
бегоем по циклу сравниваем каждое число с Х
если не одно не равно то
бегоем по циклу сравниваем 1+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 2+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 3+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 4+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 1+2+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 1+3+другое число число с Х
если не одно не равно то
..... и.т.д.
Можно оптимальнее сделать но пока первое что мне пришло в голову

HRustBB (2009-12-06 12:44:00) [9]
так так так, попродробней пожалуйсто :)

McSimm (2009-12-06 12:43:00) [10]
Двоичное представление числа отвечает на ваш вопрос.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »