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

← →
HRustBB (2009-12-06 12:36) [0]

Есть задача:
дано четыре числа 1 2 4 8. и есть число, назовем его Х, которое равно сумме двух, трех, четырех из этих чисел, либо какому нибудь одному из них. Дак вот, нужно определить из каких чисел из предложенного ряда сложенно Х. Да и кстати каждое из четырех указанных чисел участвует в сумме только один раз. Нужен алгоритм хотябы.

← →
McSimm © (2009-12-06 12:43) [1]

Двоичное представление числа отвечает на ваш вопрос.

← →
HRustBB (2009-12-06 12:44) [2]

так так так, попродробней пожалуйсто :)

← →
HRustBB (2009-12-06 12:55) [3]

ааа, comprento, спасибо досвиданья

← →
AIK © (2009-12-06 12:55) [4]

сперва
бегоем по циклу сравниваем каждое число с Х
если не одно не равно то
бегоем по циклу сравниваем 1+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 2+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 3+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 4+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 1+2+другое число число с Х
если не одно не равно то
бегоем по циклу сравниваем 1+3+другое число число с Х
если не одно не равно то
..... и.т.д.
Можно оптимальнее сделать но пока первое что мне пришло в голову

← →
Inovet © (2009-12-06 13:04) [5]

> [4] AIK © (06.12.09 12:55)
> бегоем по циклу

А в нём shr 1 and 1

← →
McSimm © (2009-12-06 13:16) [6]

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

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

← →
Юрий Зотов © (2009-12-07 00:33) [7]

> Тест на интуицию

:o)

на интуицию препода.

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

Внимание! Тест на интуицию :) Найти похожие ветки