Автор | Сообщение |
|
| Администратор
|
Сообщение: 2
|
|
Отправлено: 24.01.12 19:12. Заголовок: [C3] Решение через дерево
Вопрос: цитата: | Здравствуйте! Есть вопрос по заданию С3: "У исполнителя Увеличитель две команды,которым присвоены номера: 1. прибавь 1; 2. умножь на 4. Сколько есть программ,которые число 1 преобразуют в число 32? Ответ обоснуйте. " Так вот, решаю это задание всегда "деревом" возможных решений,получается быстро и наглядно. Но на пробном ЕГЭ в школе учительница поставила 0 баллов и сказала что это неправильно, и, ссылаясь на правильное решение "Таблицей" с Вашего сайта, закончила разговор...=( Прошу рассудить, и сказать, имеет ли право на жизнь решение "деревом" задания С3... |
|
В ответ на ваш вопрос приведу выдержку из критериев оценки из опубликованного демо-варианта: цитата: | "В частности, оценка в 2 балла выставляется в случае, если просто перечислены все правильные программы и не доказано отсутствие других программ, кроме приведенных." |
|
Так что ваше решение (если, конечно, получен правильный ответ) попадает целиком под этот пункт, то есть за решение с помощью дерева (перечислением) должны поставить 2 балла. Ответ М.А. Ройтберга: цитата: | Здравствуй, ….! Мне проще обращаться на «ты», если что – извини(те) ). Начну с конца. Никогда нельзя быть уверенным, что известны все правильные решения (в смысле – все рассуждения, приводящие к правильному решению). Вот правильный ответ может быть известен и может быть доказано, что других ответов нет. Таким образом, наличие определенного решения (например, «Таблицей»), само по себе не означает, что какое-то другое рассуждение (например, «деревом возможных решений» ) неправильное. Но является ли решение правильным, нельзя узнать, не увидев самого решения. Если оно приводит к неправильному ответу, - значит, точно неправильное. Но даже правильный ответ не гарантирует правильности решения. Более того. Может быть, решение (которое имелось в виду) было правильным, но при записи не были разобраны какие-то варианты. Построение дерева возможностей как раз часто и приводит к подобным ошибкам (а таблица от них защищает). Вывод. Если хочешь, пришли мне свое решение, я посмотрю и отвечу, правильное ли оно. Напоследок – несколько вопросов/замечаний. 1. Разобрался ли ты в решении «Таблицей»? В нем полезно разобраться независимо от ЕГЭ. Если не разобрался – напиши, что непонятно. 2. Даже, если твое решение правильное, сдавая экзамен, стоит помнить, что экзаменатор – человек. И, значит, (при прочих равных условиях) – писать то решение, в котором экзаменатору будет легче разобраться. В данном случае, - это, видимо, решение «Таблицей». 3. Ты пишешь: «Так вот, решаю это задание всегда "деревом" возможных решений, получается быстро и наглядно» Насчет «наглядно» - возможно, а насчет «быстро» - сомневаюсь. Я вот сделал ошибку при построении дерева. Если бы не знал правильный ответ (быстро заполнил таблицу), - пропустил бы. Успехов! |
|
|
|
|
Новых ответов нет
, стр:
1
2
3
4
All
[см. все]
|
|
|
Отправлено: 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 программы. Как быть в этом случае?
|
|
|
|
| Администратор
|
Сообщение: 7
|
|
Отправлено: 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. Заголовок: Я решаю "обратны..
Я решаю "обратным сокращенным деревом", решается в минуту, объясняется за три. Всякие таблицы и формулы отдыхают.
|
|
|
|
| Администратор
|
Сообщение: 32
|
|
Отправлено: 31.01.12 21:17. Заголовок: Сидоров пишет: Я реш..
Сидоров пишет: цитата: | Я решаю "обратным сокращенным деревом", решается в минуту, объясняется за три. Всякие таблицы и формулы отдыхают. |
|
Как я понимаю, сокращение идет за счет того, что умножение не всегда обратимо. А если нет умножения и несколько сотен решений?
|
|
|
|
Отправлено: 31.01.12 21:20. Заголовок: Насчет умножения не ..
Насчет умножения не понял, сорри. Под "сокращением" имею ввиду непрорисовку ветвей, выходящих из узлов, для которых количество путей к цели уже вычислено. "Обратным" я называю дерево, потому что ищу кол-во путей от конца к началу обратными операциями.
|
|
|
|
| Администратор
|
Сообщение: 33
|
|
Отправлено: 31.01.12 21:25. Заголовок: Сидоров пишет: Насче..
Сидоров пишет: цитата: | Насчет умножения не понял, сорри. |
|
Если идти от конечного значения, то, например, при наличии команды "умножь на 3" ветвление будет только тогда, когда число делится на 3. Было бы интересно посмотреть на решение с большим количеством программ (>100). И еще не совсем ясно, как доказывать, что других нет и ничего не пропущено (чтобы получить 3 балла).
|
|
|
|
|
Отправлено: 31.01.12 21:35. Заголовок: Дайте мне условие, н..
Дайте мне условие, на примере которого я могу показать решение. Насчет "как доказывать" - я строю полное дерево вариантов, как мне доказывать его полноту!?
|
|
|
|
| Администратор
|
Сообщение: 34
|
|
Отправлено: 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. Можно еще подсчитывать и указывать количество путей для чисел "основного ствола", получится пресловутая таблица. Фактически, это схематическая визуализация индукции. С "двухоперационными" примерами вообще элементарно выходит.
|
|
|
|
| Администратор
|
Сообщение: 35
|
|
Отправлено: 31.01.12 22:46. Заголовок: Сидоров пишет: снача..
Сидоров пишет: цитата: | сначала пишу "ствол" с 12 до 1, потом иду снизу вверх, рисуя ответвления. |
|
По сути то же динамическое программирование, только форма записи другая.
|
|
|
Новых ответов нет
, стр:
1
2
3
4
All
[см. все]
|
|