Отправлено: 22.05.12 15:39. Заголовок: C3 может ли быть такое задание?

Константин Юрьевич, может ли в С3 быть такое задание?
У исполнителя 2 команды:
1. отними 1
2. раздели на 2
Сколько есть программ, которые число 16 преобразуют в число 1? Ответ обоснуйте

как нужно правильно начать отвечать если хочется использовать то доказательство, которому научились для аналогичных обратных задач:

У исполнителя 2 команды
1. прибавь 1
2. умножь на 2
РЕШЕНИЕ:
Пусть К количество искомых команд. Начнем решать задачу последовательно для чисел 1, 2, 3 и т.д.
К(1) = 1 (пустая программа)
К(2) = 2 (+1, *2)
К(3) = 1 (+1+1, *2+1)
Для каждого следующего числа рассмотрим из какого числа оно может быть получено за одну команду исполнителя. Если число N не делится на 2, то KN = К(N-1), если делится на два, то K(N) = K(N-1)+K(N/3). Согласно этим формулам заполним таблицу для остальных чисел:
... далее таблица

 Отправлено: 22.05.12 15:52. Заголовок: Хижняк пишет: может..

Хижняк пишет:

цитата:

может ли в С3 быть такое задание? У исполнителя 2 команды: 1. отними 1 2. раздели на 2 Сколько есть программ, которые число 16 преобразуют в число 1?

Теоретически да, но нужно уточнить, что команда 2 может быть использована только тогда, когда число делится на 2. Или указать, что при выполнении команды 2 результат округляется (вверх или вниз).

 Отправлено: 22.05.12 15:58. Заголовок: А как тогда доказыва..

А как тогда доказывать? Имеется в виду для случая, когда 2-я команда уточнена (число делится)...

 Отправлено: 22.05.12 16:14. Заголовок: Хижняк пишет: А как ..

Хижняк пишет:

цитата:

А как тогда доказывать? Имеется в виду для случая, когда 2-я команда уточнена (число делится)...

Я бы шел от начального числа 16 к конечному. Доказательство такое же, как в демо-варианте, но числа уменьшаются от 16 до 1. Вот идея:

 R[16] := 1; 
 for k:=15 downto 1 do begin 
   R[k]:=R[k+1]; 
   if k*2 <= 16 then R[k]:=R[k]+R[k*2]; 
 end; 
 writeln(R[1]);

У меня получился ответ 36.

 Отправлено: 22.05.12 16:32. Заголовок: Да, получается все т..

Да, получается все так же нужно доказывать.. только с конца :) Спасибо Вам большое! Давно мучилась этим вопросом

 Отправлено: 23.05.12 10:47. Заголовок: Хочу все же привести..

Хочу все же привести решение, хочется знать, что нужно доработать, где изменить формулировки, что нужно добавить на 3 балла.

Будем решать поставленную задачу последовательно для чисел 16...1. Количество программ, которые преобразуют
число 16 в число n, будем обозначать через R(n). Число 16 можно получить двумя способами (из 17, вычетанием единицы. и из 32, деленимем на два).
Значит, R(16) = 2. Для каждого следующего числа рассмотрим, из какого
числа оно может быть получено за одну команду исполнителя. Если число не
делится на два, то оно может быть получено только из предыдущего с
помощью команды "вычти 1". Значит, количество искомых программ для
такого числа равно количеству программ для предыдущего числа: R(i) = R(i-
1). Если число на 2 делится, то вариантов последней команды два: вычти 1
и подели на 3, тогда R(i) = R(i+1) + R(i*2). Заполним соответствующую
таблицу по приведенным формулам слева направо:

[здесь будет таблица, одна графа будет выглядеть так. красиво ли? ]

Итого,
Ответ: 36 решений.

 Отправлено: 23.05.12 10:56. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

Число 16 можно получить двумя способами (из 17, вычетанием единицы. и из 32, деленимем на два). Значит, R(16) = 2.

а при чем здесь 17 и 32, сказано-же 16 исходное число

 Отправлено: 23.05.12 11:04. Заголовок: oval пишет: а при ч..

oval пишет:

цитата:

а при чем здесь 17 и 32

но я же сказал в решении, что буду считать последовательно, а значит, я буду перебирать все возможные варианты. отсюда и следуют числа 17, 32, 28, 24, 20 и т.д. В таблицу я их заносить не хотел. Решил такой способ записи, как показано на картинке, использовать. Когда появляется число, не входящее в наш отрезок [16;1], прибавляем по единице. А что, неточность где-то?

 Отправлено: 23.05.12 11:21. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

А что, неточность где-то?

У любой программы есть входные и выходные данные, для данной программы входными данным является число 16, числа больше 16 не должны вас волновать.
Если программа пустая(она одна) то из 16 на входе мы получим 16 на выходе, но программа одна, поэтому R(16)=1.(обе команды уменьшают входное число, следовательно, из чисел меньше 16 мы 16 получить не можем)
Для обычных задач, где надо из 1 получить что-то с помощью +/*, вы тоже будете рассматривать 0 и отрицательные числа?

 Отправлено: 23.05.12 11:35. Заголовок: не так начал. :sm38:..

не так начал.

 Отправлено: 23.05.12 16:04. Заголовок: тогда, вот так Буде..

тогда, вот так

Будем решать поставленную задачу последовательно для чисел 16...1. Количество программ, которые преобразуют
число 16 в число n, будем обозначать через R(n). Зададим начальное число 16 - одна программа.
Значит, R(16) = 1. Для каждого следующего числа рассмотрим, из какого
числа оно может быть получено за одну команду исполнителя. Если число не
делится на два, то оно может быть получено только из предыдущего с
помощью команды "вычти 1". Значит, количество искомых программ для
такого числа равно количеству программ для предыдущего числа: R(i) = R(i-
1). Если число на 2 делится и при умножении числа на два, число не превышает 16, то вариантов его получения два: вычти 1
или подели на 2, тогда R(i) = R(i+1) + R(i*2). Заполним соответствующую
таблицу по приведенным формулам слева направо:
16 1
15 1
14 1
13 1
12 1
11 1
10 1
9 1
8 2
7 3
6 4
5 5
4 7
3 11
2 18
1 36

Итого, ответ 36.

Что не учел/не разъяснил в этот раз?

 Отправлено: 23.05.12 17:31. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

Зададим начальное число 16 - одна программа.

цитата:

Если число не делится на два, то оно может быть получено только из предыдущего с помощью команды "вычти 1". Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i- 1).

цитата:

Если число на 2 делится и при умножении числа на два, число не превышает 16,.....

мне не нравятся эти строки попробуйте сформулировать это по-другому, но мысль правильная

 Отправлено: 23.05.12 17:56. Заголовок: по первому выделенно..

по первому выделенному фрагменту - зададим начальное значение - одна программа. в официальном решении такая фраза стоит "Число C у нас уже есть,
значит, его можно получить с помощью “пустой” программы" - пустая программа, которая весит единицу - тоже плоховато звучит)

второй фрагмент - копипаст из официального решения

третий фрагмент - если число при умножении на два не превышает 16. кстати, в том выделенном фрагменте ошибка. число не обязательно должно делиться на два

 Отправлено: 23.05.12 18:06. Заголовок: 1ро4ка_двадва88 пише..

1ро4ка_двадва88 пишет:

цитата:

"Число C у нас уже есть, значит, его можно получить с помощью одной “пустой” программы"

и обе команды уменьшают исходное число, следовательно, из чисел меньше 16 мы 16 получить уже не сможем
поэтому R(16) = 1

цитата:

второй фрагмент - копипаст из официального решения третий фрагмент - если число при умножении на два не превышает 16. кстати, в том выделенном фрагменте ошибка. число не обязательно должно делиться на два

в третьем фрагменте ошибку увидели, а во втором нет

 Отправлено: 23.05.12 18:12. Заголовок: окей. Если число пр..

окей.
Если число при умножении на два превыышает 16, то оно может быть получено только из предыдущего с
помощью команды "вычти 1". Значит, количество искомых программ для
такого числа равно количеству программ для предыдущего числа: R(i) = R(i-
1).

oval пишет:

цитата:

из чисел меньше 16 мы 16 получить уже не сможем

хорошее замечание.