| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Флейм > Разминка. Задачка |
| Автор: dcc0 4.10.2014, 19:43 |
| Сколькими способами можно прочитать слово "аналогия" на данном ромбе с отрезанной нижней вершиной? (имеются в виду все кратчайшие пути): |
| Автор: irinazanuda 4.10.2014, 20:26 |
| 250 Добавлено через 1 минуту и 8 секунд PS: я без формул=так считала |
| Автор: ksnk 4.10.2014, 21:14 |
| 70 ? Добавлено через 1 минуту Начинать можно только с верхней А, или и из А третьего ряда тоже ? |
| Автор: dcc0 4.10.2014, 21:36 | ||
В книжке не сказано. Ответа в книжке тоже нет. У меня получилось 70, если идти с вершины. А про третий ряд я не подумал. А ведь и правда. UPD: Причем можно возвращаться от любого А к Н потом к тому же А. |
| Автор: ksnk 4.10.2014, 21:40 | ||
А наука по этому поводу есть, или тупо перебором? Я - тупо перебрал
верхний массив - исключительно для поясления алгоритма. в работе не участвует |
| Автор: irinazanuda 4.10.2014, 21:54 |
| Ну, вы что ? Оболдели так мало))).. даже при беглом куча вариантов.. вот смотрите... сейчас скопирую и покажу варианты.. то же мне математики |
| Автор: dcc0 4.10.2014, 21:59 | ||
Тут зависит от широты условия, оно такое, как в первом сообщении. Но тогда ваша правда. Так как условие не говорит - идти только от вершины. Тогда, наверное, больше 250. Если, я как я уже сказал - шаг вперед, шаг назад - от А к Н и обратно к тому же А |
| Автор: irinazanuda 4.10.2014, 22:07 | ||
это ключевая фраза)) там от верхней А идти, сначала влево там пять вариантов, потом также на одну буква меньше, потом зигзагами, в том же самом направление.. т.к. ромб (сначала елозимся в треугольнике верхнем, потом умножаем на два (т.к. зеркально |
| Автор: dcc0 4.10.2014, 23:14 | ||
| Все-таки могли бы авторы в детской книжке попроще задание привести. Кстати, можно придумать разминку на внимание покороче:
|
| Автор: ksnk 4.10.2014, 23:32 | ||||
 Не зеркально.Если можно начинать с - 3-го ряда - получится в 3 раза больше вариантов, чем при начале только с первого. Доказательство нужно? При 70 вариантах - 210, не больше 250 все равно... Решение, если не перебором, и с верхнего ряда, выглядит так. Ставим всместо каждой буквы количество путей, которыми до нее можно дойти. Вместо первой ставим 1. До второго ряда можно дойти - до правой 1 и до левой 1, до третьего ряда - 1,2,1 и так далее. каждое число в ряду оказывается суммой находящихся "над ним". Итого получится
сумма всех числе ряда и есть решение |
| Автор: dcc0 4.10.2014, 23:51 |
| Нет, треугольник Паскаля подходит только если идти с вершины. А с 3 ряда вариантов много больше. Особенно если учесть, что можно делать шаг назад |
| Автор: irinazanuda 5.10.2014, 00:09 |
| Вы с таким умным видом говорите.. НО идти можно по разному.. например, от вершины вправо до упора, ессно потом вниз, второй раз идём также доходя одной буквы, там их вариантов 5 в одном направлении, затем опять от вершины но на другую букву Н, а поворот тудаже по тем же буквам, т.е. один маленький зигзаг, потом другой вариант... после использования кучи от двух н переходим на три буквы но зигзиги опять вправо по проторенной дороге.. ну, вы поняли... дети.. там много Добавлено через 2 минуты и 33 секунды ksnk, несмотря на слово подсветка, которая вызывает душевный трепет... написано не верно |
| Автор: ksnk 5.10.2014, 01:24 | ||||
Не "много больше", а ровно в 3 раза больше. Для каждого "слова", начинающегося с первой буквы, существует еще 2 слова, у которых первая буква начинается с 3-го.
Какие ваши доказательства? Слово подсветка генерируется форумом. |
| Автор: irinazanuda 5.10.2014, 02:07 |
| ksnk, Всё равно 250 раз!! и всё |
| Автор: dcc0 5.10.2014, 05:57 |
| 280 по примерным подчетам |
| Автор: ksnk 5.10.2014, 11:48 |
| Вот 35 решений, проходящих через правую букву H. Еще ровно столько же, проходящих через левую H Для каждого такого решения есть еще по 2, у которых вместо первой буквы, старт слова идет с третьего ряда. А у вас какие доказательства? |
| Автор: dcc0 5.10.2014, 12:34 |
| Берем только от вершины - 70. Согласны? Берем третью строку. Первый промежуточный результат: 1. Берем А слева 2. Идем от него к Н 3. И возвращаемся к тому же А 4. Просчитываем все варианты с учетом такого хода 5. С А справа будет тоже самое, ибо симметрия Поэтому умножаем на 2 Второй промежуточный результат: 1. Берем А слева 2. Движемся к Н 3. От Н движемся к центральному А 4. Просчитываем все варианты с уч. такого хода. 5. Умножаем на два Третий промежуточный результат: 1. Берем центральное А 2. Идем вверх к Н слева 3. Возвращаемся к тому же А 4. Просчитываем все варианты 5. Умножаем на 2, так как тоже самое делаем с Н справа. Четвертый промежуточный результат: 1. Берем центральное А 2. Идем вверх к Н слева 3. Идем к А вниз слева 4. Просчитываем все варианты. 5. Умножаем на 2. А вот после этого уже суммируем первый результат - с А, которое на вершине с промежуточными. |
| Автор: ksnk 5.10.2014, 13:39 |
| dcc0, Ну и? Можно по моей картинке считать. Неужели получается другой результат? Мой ответ - для каждого из 35 решений на рисунке, проходящих через правую Н существует еще 2, начинающихся в 3-й строке. БОЛЬШЕ НЕТ! Итого - всего 3*35*2=210 решений. |
| Автор: dcc0 5.10.2014, 15:26 |
| Я не могу понять. Вы вот это учли? |
| Автор: dcc0 5.10.2014, 15:26 |
| Или только такие варианты: |
| Автор: ksnk 5.10.2014, 15:52 |
| Конечно. Если мы с верхней буквы придем в левую букву Н - мы получим 35 возможностей прочитать слово. Точно так же, если мы придем в левую Н из обоих возможных А 3-го ряда - мы получим для каждой те же 35 возможностей. Всего - 3*35 вариантов. Для правой Н то же самое - Итого 2*3*35 = 210. |
| Автор: dcc0 5.10.2014, 17:03 |
| После того, как вы написали про 3 ряд, я сразу предположил, что 210, но почему-то есть сомнения. UPD: Да, как ни считай = 210 |
| Автор: Bulat 6.10.2014, 14:13 | ||
Я ленивый - одним способом - визуально!!!  |
