Форум » Теория игр » C3 может ли быть такое задание? » Ответить

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). Согласно этим формулам заполним таблицу для остальных чисел: ... далее таблица

Ответов - 14

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

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

Поляков: Хижняк пишет: А как тогда доказывать? Имеется в виду для случая, когда 2-я команда уточнена (число делится)... Я бы шел от начального числа 16 к конечному. Доказательство такое же, как в демо-варианте, но числа уменьшаются от 16 до 1. Вот идея: [pre2] 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]);[/pre2]У меня получился ответ 36.


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

1ро4ка_двадва88: Хочу все же привести решение, хочется знать, что нужно доработать, где изменить формулировки, что нужно добавить на 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 решений.

oval: 1ро4ка_двадва88 пишет: Число 16 можно получить двумя способами (из 17, вычетанием единицы. и из 32, деленимем на два). Значит, R(16) = 2. а при чем здесь 17 и 32, сказано-же 16 исходное число

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

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

1ро4ка_двадва88: не так начал.

1ро4ка_двадва88: тогда, вот так Будем решать поставленную задачу последовательно для чисел 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. Что не учел/не разъяснил в этот раз?

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

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

oval: 1ро4ка_двадва88 пишет: "Число C у нас уже есть, значит, его можно получить с помощью одной “пустой” программы" и обе команды уменьшают исходное число, следовательно, из чисел меньше 16 мы 16 получить уже не сможем поэтому R(16) = 1 второй фрагмент - копипаст из официального решения третий фрагмент - если число при умножении на два не превышает 16. кстати, в том выделенном фрагменте ошибка. число не обязательно должно делиться на два в третьем фрагменте ошибку увидели, а во втором нет

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



полная версия страницы