А я решаю задачи в Excel’e
Компьютерра, 1998-1999?
Алексей Демаков.
В свободную минуту люблю я порешать красивые задачи или головоломки. А если рядом оказывается компьютер, стараюсь и его приспособить для этой цели.
Во-первых, компьютер, точнее Internet, может служить источником задач — все приведенные ниже примеры взяты из Panthera’s Puzzle Contest — постоянно действующего конкурса по решению головоломок. Приятно, что правильность ответа проверяется компьютером и результат становится известен сразу же.
Во-вторых, компьютер всегда привлекал меня как очень аккуратный черновик — напишешь на бумажке цифру неразборчиво и все решение может оказаться неверным. Можно, конечно, и на компьютере ошибиться в вычислениях, написать не ту цифру. Вот здесь-то и родилась идея переложить вычисления на «железяку» — пусть она считает, а я думать буду! Программу каждый раз писать слишком хлопотно, специализированных математических пакетов у меня под рукой не было, да и не нужны они оказались — для моих нужд идеально подошел MS Excel! В самом деле, записав исходные данные в ячейках таблицы, в других можно разместить формулы, соответствующие действиям при решении задачи.
Задача: Какое минимальное и максимальное количество Пятниц Тринадцатых может быть в году?
Решение: С точки зрения математики, ничего сложного в этой задаче нет — надо найти порядковые номера от начала года всех тринадцатых чисел, а потом посмотреть на их остатки при делении на 7 — два дня в году одновременно могут быть пятницами только когда между ними проходит целое число недель, то есть их порядковые номера имеют один и тот же остаток при делении на 7. И еще надо не забыть про високосные годы!
Первая строка для удобства содержит названия месяцев. Вторая — количество дней в этих месяцах. Третья — количество дней, прошедших с начала года. Четвертая — остаток при делении на 7 порядкового номера тринадцатого числа соответствующего месяца.
A | B | C | D | E | F | G | H | I | J | K | L | |
1 | Jan | Feb | Mar | Apr | May | Jun | Jul | Aug | Sep | Oct | Nov | Dec |
2 | 31 | 28 | 31 | 30 | 31 | 30 | 30 | 31 | 30 | 31 | 30 | 31 |
3 | =A2 | =A3+B2 | ||||||||||
4 | =MOD(13;7) | =MOD(A3+13;7) |
Формулы из ячеек B3-B4 надо скопировать в столбцы C-L. В результате получится следующая таблица:
A | B | C | D | E | F | G | H | I | J | K | L | |
1 | Jan | Feb | Mar | Apr | May | Jun | Jul | Aug | Sep | Oct | Nov | Dec |
2 | 31 | 28 | 31 | 30 | 31 | 30 | 31 | 31 | 30 | 31 | 30 | 31 |
3 | 31 | 59 | 90 | 120 | 151 | 181 | 212 | 243 | 273 | 304 | 334 | 365 |
4 | 6 | 2 | 2 | 5 | 0 | 3 | 5 | 1 | 4 | 6 | 2 | 4 |
Вспомним теперь про существование високосных лет и исправим число дней в феврале. Excel тут же пересчитает всю таблицу:
A | B | C | D | E | F | G | H | I | J | K | L | |
1 | Jan | Feb | Mar | Apr | May | Jun | Jul | Aug | Sep | Oct | Nov | Dec |
2 | 31 | 29 | 31 | 30 | 31 | 30 | 31 | 31 | 30 | 31 | 30 | 31 |
3 | 31 | 60 | 91 | 121 | 152 | 182 | 213 | 244 | 274 | 305 | 335 | 366 |
4 | 6 | 2 | 3 | 6 | 1 | 4 | 6 | 2 | 5 | 0 | 3 | 5 |
Ответ: Минимальное число Пятниц Тринадцатых равно 1, максимальное — 3.
Стали видны некоторые преимущества Excel — если задать ход решения один раз, результат легко получить для любых исходных значений.
В следующей задаче ситуация несколько иная — формулы для решения имеются, а вот исходные данные нужно подбирать:
Задача: 20 чисел, a1, a2, …, a20, таковы что:
- a2 = 12*[a1/10] + a1 — 1
- a3 = a2 + a1, a4 =
a3 + a2, …, a20 = a19 + a18 - a20 = 167761
Найдите эти числа. ([ ] — целая часть)
Решение: Занесем формулы в соответствующие ячейки. Надо подобрать значение A1 так, чтобы выполнялось последнее равенство: A20 = 167761. Это нетрудно сделать вручную, но я воспользуюсь случаем, чтобы рассказать как с помощью Excel можно автоматизировать подобные вещи. Есть такое средство — пункт меню Tools/Goal Seek. В нем можно задать ячейку и значение, которое хотелось бы в ней получить, а также ячейку, которую можно изменять, чтобы добиться результата. Нам надо получить в ячейке A20 значение 167761. А менять можно значение в ячейке A1. В результате получается, что A1 = 18.
|
|
В предыдущих задачах Excel экономил время, освобождал от значительного количества нудных вычислений, но ход решения задачи от этого не менялся, все действия можно было проделать и на бумажке. А теперь поговорим о задаче, для которой есть два различных метода решения — первым можно воспользоваться и без Excel, а второй использует MS Excel Solver — средство для автоматического подбора значений.
Задача: A, B, C, D, E, F и G сидят за круглым столом; У каждого из них есть определенное количество яблок. A дал остальным шести столько яблок, сколько у каждого из них было. Затем B поступил таким же образом. И так далее до G. После этого у каждого из них оказалось по 128 яблок. А сколько яблок было у каждого из них в начале?
Решение:
Первый способ:
A | B | C | D | E | F | G | |
1 | 128 | 128 | 128 | 128 | 128 | 128 | 128 |
2 | =A1/2 | =(SUM($A1:$G1)+G1)/2 | |||||
3 | |||||||
4 | |||||||
5 | |||||||
6 | |||||||
7 | |||||||
8 |
Метод решения таких задач иногда называют анализом с конца. В первой строке записаны исходные данные — то, что получилось в конце, а каждая следующая строчка описывает ситуацию перед очередным дележом яблок. Тот, кто получал яблоки, на предыдущем шаге имел вдвое меньше, а тот кто отдавал — на столько яблок больше, сколько было у всех остальных. Вручную ввести придется только две формулы — ту, что в ячейке A2 (и скопировать ее во все ячейки прямоугольника A2-G8), а затем ту, что в G2 ее надо копировать в ячейки диагонали G2-A8. Напомню, что A1 — это относительный адрес ячейки, поэтому, например, в ячейке E7 будет стоять формула E6/2. Знак доллара в $A1 и $G1 указывает, что адрес столбца абсолютный и при копировании в другие ячейки не меняется. В результате получится таблица, последняя строка которой — искомые числа.
A | B | C | D | E | F | G | |
1 | 128 | 128 | 128 | 128 | 128 | 128 | 128 |
2 | 64 | 64 | 64 | 64 | 64 | 64 | 512 |
3 | 32 | 32 | 32 | 32 | 32 | 480 | 256 |
4 | 16 | 16 | 16 | 16 | 464 | 240 | 128 |
5 | 8 | 8 | 8 | 456 | 232 | 120 | 64 |
6 | 4 | 4 | 452 | 228 | 116 | 60 | 32 |
7 | 2 | 450 | 226 | 114 | 58 | 30 | 16 |
8 | 449 | 225 | 113 | 57 | 29 | 15 | 8 |
Второй способ:
Предположим, что начальные значения уже найдены. Запишем, как изменялось количество яблок при дележах. Опять же существуют два случая — для того, кто отдавал яблоки при этом дележе, и для всех остальных. Формула для второго случая записана в ячейке G2, ее надо скопировать во все ячейки прямоугольника A2-G8, а поверх нее во все клетки диагонали A2-G8 скопировать формулу из ячейки A2.
A | B | C | D | E | F | G | |
1 | |||||||
2 | =2*A1-SUM($A1:$G1) | =2*G1 | |||||
3 | |||||||
4 | |||||||
5 | |||||||
6 | |||||||
7 | |||||||
8 |
Теперь можно пользоваться старшим братом Goal Seek — Tools/Solver. Этот инструмент умеет подбирать значения нескольких ячеек так, чтобы выполнялись определенные условия. У нас есть семь условий — значения в ячейках A8-G8 должны равняться 128. Для этого надо подбирать значения A1-G1. Задав все необходимое, можно запустить Решателя, который, если не ошибаюсь, за 8 итераций найдет решение.
A | B | C | D | E | F | G | |
1 | 449 | 225 | 113 | 57 | 29 | 15 | 8 |
2 | 2 | 450 | 226 | 114 | 58 | 30 | 16 |
3 | 4 | 4 | 452 | 228 | 116 | 60 | 32 |
4 | 8 | 8 | 8 | 456 | 232 | 120 | 64 |
5 | 16 | 16 | 16 | 16 | 464 | 240 | 128 |
6 | 32 | 32 | 32 | 32 | 32 | 480 | 256 |
7 | 64 | 64 | 64 | 64 | 64 | 64 | 512 |
8 | 128 | 128 | 128 | 128 | 128 | 128 | 128 |
Получается, что «железяке» можно поручать довольно трудные задания, говоря что делать, а не как делать. Впрочем, думать мне и самому нравится, поэтому первое решение мне больше по душе. Да и на кнопки нажимать там надо меньше.
Закончу рассказ о необычном использовании Excel задачей, которая мне особенно понравилась. Она требует некоторого знания английского языка, но переводить не хочется.
Задача: Расшифруйте текст и следуйте полученным инструкциям:
HNT MHMT QRS RGG DPKSJ YT HNZJ QEOESOEQZ DTKT MTIRGMG DZHN LYUQVM WTHHTK LJNLKYKJKYRT EBMNTKJ, NJK DZHN GYAAMOMTK XTBJ. CRJ IZRS KZM XTB RA Q VMKKMO JGUJHZHGHZPR ICQZMO UB FOYKYTS HNT EVQZENMK PR RTM KPD ETG HNT MTIRGMG FQKZQRHJ RT HNT NRKKRU. TRHTK KZM HDP WMCL, UPHN IRUURT TROWZJN FROGL, JTMQKQHTS NC Q LQEIM HP UMMK DZHN LJIIMLL.
Решение: Очень похоже, что в этой задаче использован самый простой шифр, при котором каждая буква алфавита заменяется на некоторую другую. Известен метод расшифровки, основанный на анализе частоты появления той или иной буквы. Решив задачу я порадовался, что не воспользовался им — этот метод
здесь не работает!
А что, если занести каждую букву шифра в отдельную ячейку таблицы Excel, да еще сделать так, чтобы можно было быстро увидеть результат подстановки одной буквы вместо другой? Тут мне помог текстовый редактор, в котором каждую букву шифра я заменил на последовательность <TAB>=L1, где L — произвольная буква. Исключение составляют пробелы — они были заменены на <TAB><пробел>. Если скопировать через буфер обмена полученный текст в Excel, получится то, что было необходимо — каждая ячейка будет содержать формулу, так как символы табуляции <TAB> воспринимаются Excel’ем как признак перехода в следующую ячейку. Текст можно поместить в любом месте таблицы, главное, чтобы ячейки A1-Z1 остались свободными — в них будут
стоять результаты подстановки. Например, если ячейка R1 содержит букву D, это значит, что все буквы R шифра (они ссылаются на ячейку R1), будут заменены на букву D. Для начала в A1-Z1 можно поставить буквы A-Z — это дает исходный шифр.
Далее наступает творческая часть работы — я же говорил, считать будет «железяка», а думать все равно придется человеку! Надо угадать хотя бы несколько первых букв, чтобы стало более-менее понятно, что делать дальше. Это несложно для любого, кто хоть немного знаком с английским языком. Например, можно предположить, что фраза начинается с «The». Затем предположить, что седьмое слово — это «this». Тогда одиннадцатое — «with». Попробуйте сами — разгадывать шифр таким образом оказалось сплошным удовольствием. Но через некоторое время все застопорилось — оказалось, что половина слов представляет собой полную абракадабру:
THE PTPE AND NUU WORDS ?E THIS A?G?DG?AI WERE PEFNUPU WITH ??BA?P LETTER ?SH?R?RSR?NE ?YPHERS, HSR WITH U???PGPER KEYS. ?NS FIND RIP KEY N? A ?PRRPG SUBSTITUTION F?AIPG BY VG?R?ED THE ??AI?HPR ON NEP ROW ?EU THE
PEFNUPU VARIANTS NE THE HNRRNB. ENTER RIP TWO LP??, BOTH FNBBNE ENGLISH VNGU?, SEPARATED H? A ?A?FP TO BPPR WITH ?SFFP??.
Но из уже разгаданных обрывков удалось понять, что вторая половина фразы зашифрована по тому же принципу, но с другим ключом. Вот поэтому и бессмысленно было бы анализировать частоту появления букв! Дальнейшее было делом техники. Вот что получилось в результате:
THE EVEN AND ODD WORDS IN THIS PARAGRAPH WERE ENCODED WITH SIMPLE LETTER SUBSTITUTION CYPHERS, BUT WITH DIFFERENT KEYS. YOU FIND THE KEY OF A LETTER SUBSTITUTION CYPHER BY WRITING THE ALPHABET ON ONE ROW AND THE ENCODED VARIANTS ON THE BOTTOM. ENTER THE TWO KEYS, BOTH COMMON ENGLISH WORDS, SEPARATED BY A SPACE TO MEET WITH SUCCESS
Для получения окончательного ответа придется «обратить» подстановку — у нас оказались записаны по порядку буквы шифра, а под ними были записаны буквы, которые им соответствовали в исходном тексте, а надо записать по порядку буквы исходного текста, а под ними — соответствующие буквы шифра.
Ответ: QUESTION ENIGMAS или ENIGMAS QUESTION.
Вот так Excel из скучной и, честно говоря, почти бесполезной для меня программы превратился в любимого помощника в решении занимательных задач.
Если вы тоже любите решать задачи, обратите внимание еще на одно место, где проводится конкурс по решению задач: Web Wizard’s Math Challenge. Как и в Panthera’s Puzzle Contest ответы здесь проверяются автоматически, но система подсчета результатов другая.
22.08.1999
Метки: Excel, puzzle, Компьютерра, математика Рубрики: Наследство
7 комментариев
Любителям головоломок и программистских задачек:
http://projecteuler.net
http://javabat.com
http://uva.onlinejudge.org/index.php
http://www.spoj.pl/
http://www.topcoder.com/tc
http://acm.timus.ru/
Советы профессионала по использованию Excel: http://akteon.livejournal.com/88344.html
Здравствуйте. А вы можете решить одну задачу с построением графика?
Написать комментарий