На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



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

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 14 [только новые]


Администратор




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


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

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

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 2
ссылка на сообщение  Отправлено: 22.05.12 15:58. Заголовок: А как тогда доказыва..


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

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 353
ссылка на сообщение  Отправлено: 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.


___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



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


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

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 91
ссылка на сообщение  Отправлено: 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 решений.

Ирочка 228 Спасибо: 0 
ПрофильЦитата Ответить
постоянный участник




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


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

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


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

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 93
ссылка на сообщение  Отправлено: 23.05.12 11:04. Заголовок: oval пишет: а при ч..


oval пишет:

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


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

Ирочка 228 Спасибо: 0 
ПрофильЦитата Ответить
постоянный участник




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


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

 цитата:
А что, неточность где-то?


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

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 94
ссылка на сообщение  Отправлено: 23.05.12 11:35. Заголовок: не так начал. :sm38:..


не так начал.

Ирочка 228 Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 95
ссылка на сообщение  Отправлено: 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.

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

Ирочка 228 Спасибо: 0 
ПрофильЦитата Ответить
постоянный участник




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


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

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



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



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


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

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 96
ссылка на сообщение  Отправлено: 23.05.12 17:56. Заголовок: по первому выделенно..


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

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

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

Ирочка 228 Спасибо: 0 
ПрофильЦитата Ответить
постоянный участник




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


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

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


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

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


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

Спасибо: 0 
ПрофильЦитата Ответить



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


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

oval пишет:

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


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

Ирочка 228 Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 7362
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет