Отправлено: 24.01.12 19:12. Заголовок: [C3] Решение через дерево

Вопрос:

цитата:

Здравствуйте! Есть вопрос по заданию С3: "У исполнителя Увеличитель две команды,которым присвоены номера: 1. прибавь 1; 2. умножь на 4. Сколько есть программ,которые число 1 преобразуют в число 32? Ответ обоснуйте. " Так вот, решаю это задание всегда "деревом" возможных решений,получается быстро и наглядно. Но на пробном ЕГЭ в школе учительница поставила 0 баллов и сказала что это неправильно, и, ссылаясь на правильное решение "Таблицей" с Вашего сайта, закончила разговор...=( Прошу рассудить, и сказать, имеет ли право на жизнь решение "деревом" задания С3...

В ответ на ваш вопрос приведу выдержку из критериев оценки из опубликованного демо-варианта:

цитата:

"В частности, оценка в 2 балла выставляется в случае, если просто перечислены все правильные программы и не доказано отсутствие других программ, кроме приведенных."

Так что ваше решение (если, конечно, получен правильный ответ) попадает целиком под этот пункт, то есть за решение с помощью дерева (перечислением) должны поставить 2 балла.

Ответ М.А. Ройтберга:

цитата:

Здравствуй, ….! Мне проще обращаться на «ты», если что – извини(те) ). Начну с конца. Никогда нельзя быть уверенным, что известны все правильные решения (в смысле – все рассуждения, приводящие к правильному решению). Вот правильный ответ может быть известен и может быть доказано, что других ответов нет. Таким образом, наличие определенного решения (например, «Таблицей»), само по себе не означает, что какое-то другое рассуждение (например, «деревом возможных решений» ) неправильное. Но является ли решение правильным, нельзя узнать, не увидев самого решения. Если оно приводит к неправильному ответу, - значит, точно неправильное. Но даже правильный ответ не гарантирует правильности решения. Более того. Может быть, решение (которое имелось в виду) было правильным, но при записи не были разобраны какие-то варианты. Построение дерева возможностей как раз часто и приводит к подобным ошибкам (а таблица от них защищает). Вывод. Если хочешь, пришли мне свое решение, я посмотрю и отвечу, правильное ли оно. Напоследок – несколько вопросов/замечаний. 1. Разобрался ли ты в решении «Таблицей»? В нем полезно разобраться независимо от ЕГЭ. Если не разобрался – напиши, что непонятно. 2. Даже, если твое решение правильное, сдавая экзамен, стоит помнить, что экзаменатор – человек. И, значит, (при прочих равных условиях) – писать то решение, в котором экзаменатору будет легче разобраться. В данном случае, - это, видимо, решение «Таблицей». 3. Ты пишешь: «Так вот, решаю это задание всегда "деревом" возможных решений, получается быстро и наглядно» Насчет «наглядно» - возможно, а насчет «быстро» - сомневаюсь. Я вот сделал ошибку при построении дерева. Если бы не знал правильный ответ (быстро заполнил таблицу), - пропустил бы. Успехов!

 Отправлено: 25.01.12 08:15. Заголовок: Варианты решения С3

Добрый день.
Отрабатываем с учениками и таблицу и дерево.

Выбирают (хотя может я не доступно объяснил "Таблицу") дерево - на мой взгяд решение "деревом" :) попроще и пропостить вариант возможно, но точно так же можно допустить ошибку и в таблице.

Не понятно почему 2 балла - должно быть 3! если дерево с комментариями.

 Отправлено: 25.01.12 08:23. Заголовок: Инна

Здравствуйте! Мои ученики тоже чаще решают С3 "деревом", говорят, что им так проще. У Ройтберга, странная на мой взгляд, аргументация...

 Отправлено: 25.01.12 13:49. Заголовок: Уважаемые коллеги! ..

Уважаемые коллеги!
Разбирали эти задачи с детьми и пришли к выводу, что подобные задачи подходят под следующий шаблон:
если число N делится на А, то к общему количеству программ (способов разложений числа N) прибавить количество программ для числа N/A;
во всех остальных случаях прибавить количество программ для числа N-B, где В-число для прибавления.
Получим в общем виде формулу
K(N)=K(N-B)+K(N/A)
Например, если есть команды
1. прибавить 1
2. умножить на 3
То количество программ в общем виде запишется так
K(N)=K(N-1)+K(N/3)
Иначе, по шагам:
N=1, 0+1=1, K(N)=1
N=2, 0+1+1=2, K(N)=1
N=3, 0+1+1+1=(0+1)*3=3, K(N)=K(N-1)+K(N/3)=K(2)+K(1)=2
N=4, 0+1+1+1+1=(0+1)*3+1=4 K(N)=K(N-1)=K(3)=2
и т.д.
Если есть более 2 команд или подобные команды?
Например, для команд
1. прибавить 1
2. прибавить 3
По шаблону должно быть K(N)=K(N-1)+K(N-3)
Считаем K(0)=1
N=1 0+1=1 K(N)=K(0)=1
N=2 0+1+1=2 K(N)=K(N-1)=K(1)=1
N=3 0+1+1+1=0+3=3 K(N)=K(N-1)+K(N-3)=1+0=2
N=4 0+1+1+1+1=0+3+1=4 K(N)=K(N-1)+K(N-3)=1+2=3, а на самом деле 2 программы.
Как быть в этом случае?

 Отправлено: 25.01.12 15:46. Заголовок: kmr пишет: Считаем K..

kmr пишет:

цитата:

Считаем K(0)=1 N=1 0+1=1 K(N)=K(0)=1 N=2 0+1+1=2 K(N)=K(N-1)=K(1)=1 N=3 0+1+1+1=0+3=3 K(N)=K(N-1)+K(N-3)=1+1=2 N=4 0+1+1+1+1=0+3+1=4 K(N)=K(N-1)+K(N-3)=1+2=3, а на самом деле 2 программы.

Вы решили задачу при начальном значении 0, там 3 программы: 1111, 12 и 21:
0+1+1+1+1=0+3+1=0+1+3=4

 Отправлено: 25.01.12 14:52. Заголовок: Научите решать с пом..

Научите решать с помощью "дерева", пожалуйста.

 Отправлено: 27.01.12 12:09. Заголовок: С3 с помощью дерева

Здравствуйте! Мы решаем с помощью дерева. Не рассчитываем на 3 балла, но надеемся на 1 (ответ всегда получается правильный) или 2, указывая, что дерево отображает все возможные способы получения следующего значения возможными командами.

Пример.
Задача из МИОО, ДР №1/2011, вариант 2.
Даны две команды: 1. Прибавь1, 2. Умножь на 4. Сколько есть программ, которые число 1 преобразует в число 29.

Решение. Строим дерево так (построить намного проще, чем дать описание процесса):

Рисуем вниз ветку 1 -->2 -->… --> 29, где --> это команда «+1» (подписываем их так).
Получаем 1 программу.
От 7 рисуем ветку --> 28 (эту стрелку подписываем *4) --> 29 (стрелка +1). Получаем 1 программу.
От 6 рисуем ветку --> 24 (эту стрелку подписываем *4) --> 25… --> 29 (стрелки +1). Получаем 1 программу.
От 5 рисуем ветку --> 20 (эту стрелку подписываем *4) --> 21… --> 29 (стрелки +1). Получаем 1 программу.
От 4 рисуем ветку --> 16 (эту стрелку подписываем *4) --> 17… --> 29 (стрелки +1). Получаем 1 программу.
От 3 рисуем ветку --> 12 (эту стрелку подписываем *4) --> 23… --> 29 (стрелки +1). Получаем 1 программу.
От 2 рисуем ветку --> 8 (эту стрелку подписываем *4) --> 9… --> 29 (стрелки +1). Получаем 1 программу.
От 1 рисуем ветку --> 4 (эту стрелку подписываем *4) . Смотрим на дерево. От ветки 4 и вниз у нас 5 ответвлений. Таким образом, получаем 5 программ.

Считаем все программы: 1+1+1+1+1+1+1+5 = 12.

 Отправлено: 29.01.12 16:34. Заголовок: Построение дерева_С3

Я тоже сначала строю дерево (так учащиеся понимают быстрее), потом стараемся "заложить" это в таблицу.

 Отправлено: 31.01.12 21:13. Заголовок: Я решаю "обратны..

Я решаю "обратным сокращенным деревом", решается в минуту, объясняется за три. Всякие таблицы и формулы отдыхают.

 Отправлено: 31.01.12 21:17. Заголовок: Сидоров пишет: Я реш..

Сидоров пишет:

цитата:

Я решаю "обратным сокращенным деревом", решается в минуту, объясняется за три. Всякие таблицы и формулы отдыхают.

Как я понимаю, сокращение идет за счет того, что умножение не всегда обратимо. А если нет умножения и несколько сотен решений?

 Отправлено: 31.01.12 21:20. Заголовок: Насчет умножения не ..

Насчет умножения не понял, сорри. Под "сокращением" имею ввиду непрорисовку ветвей, выходящих из узлов, для которых количество путей к цели уже вычислено.
"Обратным" я называю дерево, потому что ищу кол-во путей от конца к началу обратными операциями.

 Отправлено: 31.01.12 21:25. Заголовок: Сидоров пишет: Насче..

Сидоров пишет:

цитата:

Насчет умножения не понял, сорри.

Если идти от конечного значения, то, например, при наличии команды "умножь на 3" ветвление будет только тогда, когда число делится на 3. Было бы интересно посмотреть на решение с большим количеством программ (>100). И еще не совсем ясно, как доказывать, что других нет и ничего не пропущено (чтобы получить 3 балла).

 Отправлено: 31.01.12 21:35. Заголовок: Дайте мне условие, н..

Дайте мне условие, на примере которого я могу показать решение.
Насчет "как доказывать" - я строю полное дерево вариантов, как мне доказывать его полноту!?

 Отправлено: 31.01.12 22:00. Заголовок: Сидоров пишет: Дайте..

Сидоров пишет:

цитата:

Дайте мне условие, на примере которого я могу показать решение.

Любая из задач 6-10 из файла C3.doc.

цитата:

Насчет "как доказывать" - я строю полное дерево вариантов, как мне доказывать его полноту!?

:-) Это пока открытый вопрос. Я пытаюсь "разговорить" разработчиков ЕГЭ по поводу того, как будет оцениваться такое решение, они обещали ответить через пару дней.

 Отправлено: 31.01.12 22:37. Заголовок: 6) У исполнителя Кал..

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

Ищется число путей от 12 до 1, сначала пишу "ствол" с 12 до 1, потом иду снизу вверх, рисуя ответвления.

 
     -2 <- x -> /3 
           | 
          -1 
   
 (84)10 - 12 - 4(4) 
  (53)9 - 11 
  (31)8 - 10 
  (19)7 - 9 - 3(3) 
  (12)6 - 8 
  (7) 5 - 7 
  (4) 4 - 6 - 2(1) 
  (3) 3 - 5 
  (1) 2 - 4 
      1 - 3 - 1 
          2 
          1 
  
 В скобках - кол-во путей от этого числа до 1. Сумма скобок и трех 1 снизу равна 225.

Можно еще подсчитывать и указывать количество путей для чисел "основного ствола", получится пресловутая таблица.
Фактически, это схематическая визуализация индукции.

С "двухоперационными" примерами вообще элементарно выходит.

 Отправлено: 31.01.12 22:46. Заголовок: Сидоров пишет: снача..

Сидоров пишет:

цитата:

сначала пишу "ствол" с 12 до 1, потом иду снизу вверх, рисуя ответвления.

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