А я решаю задачи в Excel’e

Компьютерра, 1998-1999?
Алексей Демаков.

В свободную минуту люблю я порешать красивые задачи или головоломки. А если рядом оказывается компьютер, стараюсь и его приспособить для этой цели.

Во-первых, компьютер, точнее Internet, может служить источником задач — все приведенные ниже примеры взяты из Panthera’s Puzzle Contest — постоянно действующего конкурса по решению головоломок. Приятно, что правильность ответа проверяется компьютером и результат становится известен сразу же.

Во-вторых, компьютер всегда привлекал меня как очень аккуратный черновик — напишешь на бумажке цифру неразборчиво и все решение может оказаться неверным. Можно, конечно, и на компьютере ошибиться в вычислениях, написать не ту цифру. Вот здесь-то и родилась идея переложить вычисления на «железяку» — пусть она считает, а я думать буду! Программу каждый раз писать слишком хлопотно, специализированных математических пакетов у меня под рукой не было, да и не нужны они оказались — для моих нужд идеально подошел MS Excel! В самом деле, записав исходные данные в ячейках таблицы, в других можно разместить формулы, соответствующие действиям при решении задачи.

Задача: Какое минимальное и максимальное количество Пятниц Тринадцатых может быть в году?

Решение: С точки зрения математики, ничего сложного в этой задаче нет — надо найти порядковые номера от начала года всех тринадцатых чисел, а потом посмотреть на их остатки при делении на 7 — два дня в году одновременно могут быть пятницами только когда между ними проходит целое число недель, то есть их порядковые номера имеют один и тот же остаток при делении на 7. И еще надо не забыть про високосные годы!

Первая строка для удобства содержит названия месяцев. Вторая — количество дней в этих месяцах. Третья — количество дней, прошедших с начала года. Четвертая — остаток при делении на 7 порядкового номера тринадцатого числа соответствующего месяца.


  ABCDEFGHIJKL
1JanFebMarAprMayJunJulAugSepOctNovDec
2312831303130303130313031
3=A2=A3+B2          
4=MOD(13;7)=MOD(A3+13;7)          

 
Формулы из ячеек B3-B4 надо скопировать в столбцы C-L. В результате получится следующая таблица:

 ABCDEFGHIJKL
1JanFebMarAprMayJunJulAugSepOctNovDec
2312831303130313130313031
3315990120151181212243273304334365
4622503514624

 
Вспомним теперь про существование високосных лет и исправим число дней в феврале. Excel тут же пересчитает всю таблицу:

 ABCDEFGHIJKL
1JanFebMarAprMayJunJulAugSepOctNovDec
2312931303130313130313031
3316091121152182213244274305335366
4623614625035

 
Ответ: Минимальное число Пятниц Тринадцатых равно 1, максимальное — 3.

Стали видны некоторые преимущества Excel — если задать ход решения один раз, результат легко получить для любых исходных значений.

В следующей задаче ситуация несколько иная — формулы для решения имеются, а вот исходные данные нужно подбирать:

Задача: 20 чисел, a1, a2, …, a20, таковы что:


  1. a2 = 12*[a1/10] + a1 — 1

  2. a3 = a2 + a1, a4 =
    a3 + a2, …, a20 = a19 + a18

  3. a20 = 167761

Найдите эти числа. ([ ] — целая часть)

Решение: Занесем формулы в соответствующие ячейки. Надо подобрать значение A1 так, чтобы выполнялось последнее равенство: A20 = 167761. Это нетрудно сделать вручную, но я воспользуюсь случаем, чтобы рассказать как с помощью Excel можно автоматизировать подобные вещи. Есть такое средство — пункт меню Tools/Goal Seek. В нем можно задать ячейку и значение, которое хотелось бы в ней получить, а также ячейку, которую можно изменять, чтобы добиться результата. Нам надо получить в ячейке A20 значение 167761. А менять можно значение в ячейке A1. В результате получается, что A1 = 18.

 A
1 
2=12 INT(A1/10)+(A1-1)
3=A2+A1
20=A19+A18
 A
118
229
347
20167761

В предыдущих задачах Excel экономил время, освобождал от значительного количества нудных вычислений, но ход решения задачи от этого не менялся, все действия можно было проделать и на бумажке. А теперь поговорим о задаче, для которой есть два различных метода решения — первым можно воспользоваться и без Excel, а второй использует MS Excel Solver — средство для автоматического подбора значений.

Задача: A, B, C, D, E, F и G сидят за круглым столом; У каждого из них есть определенное количество яблок. A дал остальным шести столько яблок, сколько у каждого из них было. Затем B поступил таким же образом. И так далее до G. После этого у каждого из них оказалось по 128 яблок. А сколько яблок было у каждого из них в начале?

Решение:

Первый способ:

 ABCDEFG
1128128128128128128128
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 указывает, что адрес столбца абсолютный и при копировании в другие ячейки не меняется. В результате получится таблица, последняя строка которой — искомые числа.

 ABCDEFG
1128128128128128128128
2646464646464512
33232323232480256
416161616464240128
588845623212064
6444522281166032
72450226114583016
84492251135729158

 
Второй способ:

Предположим, что начальные значения уже найдены. Запишем, как изменялось количество яблок при дележах. Опять же существуют два случая — для того, кто отдавал яблоки при этом дележе, и для всех остальных. Формула для второго случая записана в ячейке G2, ее надо скопировать во все ячейки прямоугольника A2-G8, а поверх нее во все клетки диагонали A2-G8 скопировать формулу из ячейки A2.

 ABCDEFG
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 итераций найдет решение.

 ABCDEFG
14492251135729158
22450226114583016
3444522281166032
488845623212064
516161616464240128
63232323232480256
7646464646464512
8128128128128128128128

 
Получается, что «железяке» можно поручать довольно трудные задания, говоря что делать, а не как делать. Впрочем, думать мне и самому нравится, поэтому первое решение мне больше по душе. Да и на кнопки нажимать там надо меньше.

Закончу рассказ о необычном использовании 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  Метки: , , ,   Рубрики: Наследство

7 комментариев

  1. allex - 01.01.2010

    Любителям головоломок и программистских задачек:
    http://projecteuler.net
    http://javabat.com

  2. allex - 04.01.2010

    http://uva.onlinejudge.org/index.php

  3. allex - 04.01.2010

    http://www.spoj.pl/

  4. allex - 04.01.2010

    http://www.topcoder.com/tc

  5. allex - 04.01.2010

    http://acm.timus.ru/

  6. allex - 15.02.2010

    Советы профессионала по использованию Excel: http://akteon.livejournal.com/88344.html

  7. Саня - 18.01.2013

    Здравствуйте. А вы можете решить одну задачу с построением графика?

Написать комментарий