Выполнила ученица 11 А класса Коробова Тамара Аркадьевна
Муниципальное общеобразовательное учреждение «Лицей №43»
Саранск, 2004
Моя работа будет посвящена решению головоломки, условие которой находится в книге Ж.Арсака «Программирование игр и головоломок».
Условие головоломки таково:
Выбрали два натуральных числа большие 1 и меньшие 100. Значение их произведения сообщили господину Р, а значение суммы - господину S (причем, ни один из них не знает какое число сообщили другому). Далее между господином Р и господином S произошел такой диалог:
Господин Р: Я не могу найти эти два числа.
Господин S: Я знаю, что Вам это и не удалось бы.
Господин Р: Ах так. Ну тогда я их знаю.
Господин S: Ну тогда и я тоже их знаю.
Этим диалогом загаданные числа «вычисляются» однозначно.
Я составила программу на языке Pascal, которая «анализирует» высказывания господина Р и господина S и поэтому, естественно, состоит из 4 частей:
1) первая «отбрасывает» пары, состоящие из простых чисел;
2) вторая «отбрасывает» из оставшихся пар такие, сумма которых может быть представлена в виде двух простых слагаемых;
3) третья - те пары чисел, произведение которых встречается у какой-нибудь другой пары чисел, которая, кстати, тоже будет отброшена;
4) четвертая - те пары чисел, сумма которых встречается у какой-нибудь другой пары чисел, которая, кстати, тоже будет отброшена.
Теперь о самой программе: для хранения информации о парах чисел я использую двумерный булевский массив b, в который на соответствующие места я буду записывать «истину», если пара чисел удовлетворяет условию задачи на данном шаге и, естественно, «ложь», если – нет. Кстати, чтобы числа i, j и j, i не считались дважды перебор идет только по половине таблицы.
Булевская процедура prost будет «истиной», если число х – простое и «ложью», если – составное.
Остальные пояснения находятся в ремарках самой программы.
const n=99;
m=(n-1)*n div 2;
var b: array[2..250,2..250] of boolean;
i,j,k,l,p,vs1,vs2,vs3,vs4,sum,s: word;
fin: boolean;
function prost(x: word): boolean; {истина, если х - простое число}
var da: boolean;
p: word;
begin
da:=true;
if x>2 then
for p:=2 to trunc(sqrt(x)) do if x=(x div p)*p then da:=false;
prost:=da;
end;
begin
{начинается первый шаг - будут отброшены те пары чисел,
у которых оба числа - простые}
writeln(' при n= ',n);
vs1:=0; {vs1 - количество решений после первого шага}
for i:=2 to n do
for j:=i to n do
begin
if prost(i) and prost(j) then b[i,j]:=false
else begin b[i,j]:=true; vs1:=vs1+1; end;
end;
writeln('vs1= ',vs1:5,' iz ',m);
s:=0; {s -количество решений, которые будут отбрасываться в дальнейшем}
{начинается второй шаг - будут отброшены те пары чисел i,j, сумма которых
может быть представлена в виде двух простых слагаемых}
for i:=2 to n do
for j:=i to n do
begin
if b[i,j] then
begin
sum:=i+j; fin:=false; k:=2;
while (not fin) and (k<=(sum div 2)) do
begin
if prost(k) and prost(sum-k) then fin:=true;
k:=k+1;
end;
if fin then begin b[i,j]:=false; s:=s+1; end;
end;
end;
vs2:=vs1-s; writeln('vs2= ',vs2:5,' iz ',m);
{начинается третий шаг - будут отброшены те пары чисел i,j, произведение
которых встречается у какой-нибудь другой пары чисел, которая, кстати,
тоже будет отброшена}
for i:=2 to n do
for j:=i to n do if b[i,j] and (i=98) and (j=99) then writeln(i:3,j:3);
for i:=2 to n do
for j:=i to n do
begin
if b[i,j] then
begin
p:=i*j; fin:=false; k:=2;
while k<=n do
begin
l:=k;
while l<=n do
begin
if b[k,l] and (p=k*l) and (i<>k) then
begin fin:=true; b[k,l]:=false; s:=s+1; end;
l:=l+1;
end;
k:=k+1;
end;
if fin then begin b[i,j]:=false; s:=s+1; end;
end;
end;
vs3:=vs1-s; writeln('vs3= ',vs3:5,' iz ',m);
{начинается четвертый шаг - будут отброшены те пары чисел i,j, сумма
которых встречается у какой-нибудь другой пары чисел, которая, кстати,
тоже будет отброшена}
for i:=2 to n do
for j:=i to n do
begin
if b[i,j] then
begin
sum:=i+j; fin:=false; k:=2;
while k<=n do
begin
l:=k;
while l<=n do
begin
if b[k,l] and (sum=k+l) and (i<>k) then
begin fin:=true; b[k,l]:=false; s:=s+1; end;
l:=l+1;
end;
k:=k+1;
end;
if fin then begin b[i,j]:=false; s:=s+1; end;
end;
end;
vs4:=vs1-s; writeln('vs4= ',vs4:5,' iz ',m);
for i:=2 to n do
for j:=i to n do if b[i,j] then writeln(i:4,j:4);
readln
end.
Теперь о результатах:
1) оказывается при тех условиях, которые сообщены в книге (числа более 1 и менее 100, то есть от 2 до 99 включительно, поэтому первоначально в программе константа n=99) задача имеет два решения:
(4;13) и (98;99);
2) но если условия изменить: числа от 2 до 100 включительно, то второе решение (98;99) отбрасывается на 4 шаге, так как есть две пары чисел с такой суммой: (98;99) и (97;100).
Все это побудило меня исследовать эту задачу более подробно: при каких еще значениях n эта задача будет иметь единственное решение.
Достаточно видоизменить приведенную программу (n теперь будет не константой, а переменной и взять всю программу внутрь цикла по этой переменной от 5 до 110).
Результаты оказались такие:
При достаточно малых значениях n (n<35) задача либо не имела решения (при n=5, 7, 8, 10, 11, 13, 16, 17, 20, 22, 23, 25, 28, 31, 32), либо имела только одно решение равное числам (n-1) и n (при n=6, 9, 12, 14, 15, 18, 19, 21, 24, 26, 27, 29, 30, 33, 34).
При n=35 произошел качественный скачок: теперь решения были всегда, причем при некоторых значениях n (при n=35, 37, 38, 41, 43, 46, 50, 52, 53, 55, 56, 58, 65, 67, 70, 71, 76, 77, 80, 83, 85, 88, 91, 92, 97, 98, 100, 101, 107) это было единственное решение одинаковое для всех n: (4;13), а при остальных значениях n>35 добавлялось еще одно решение: (n-1;n).
Список литературы
Ж.Арсак, «Программирование игр и головоломок», М., Наука, 1990г.
Другие работы по теме:
Решение задач на переливание на бильярдном столе
Общие свойства бильярдных систем, методы их исследования. Математическая модель бильярда, решение математической проблемы бильярда, или проблемы траектории. Типичные задачи на переливание, условие разрешимости задач, алгоритм и примеры их решения.
О хамстве
Похоже, что хамство — это и грубость, и наглость, и нахальство. Грубость выполняет функцию формы, наглость обусловливает наличие цели, нахальство же выражает особый способ действия.
Оригинальные приемы почтовой рекламы
Ввиду высокой эффективности правильно организованной почтовой рекламы, специалисты разработали различные оригинальные подходы к ее проведению. В этой статье вы найдете для себя немало любопытных подсказок.
Как поумнеть или поглупеть на работе
Неинтересная работа может сделать человека глупее. Как полагают норвежские ученые, деградация является следствием однообразной и монотонной деятельности. Мозг «расслабляется» и начинает работать в режиме автопилота.
Ребенок в старшем дошкольном возрасте
На седьмом году жизни ребенок начинает осознавать свое место среди других людей, у него формируется внутренняя социальная позиция и стремление к соответствующей его потребностям новой социальной роли.
Преодоление барьеров в обучении
На пути обучения воздвигаются многочисленные барьеры. Изучим самые распространенные препятствия на пути к обучению, а также рекомендации по их преодолению.
Развитие творческих способностей
Творчество — это решение проблем, порождение новых идей, стремление научиться большему, думать о деле иначе и делать его лучше. А гениальность, несмотря на кажущуюся сложность, представляет собой то же самое, только доведенное до совершенства.
Кибераддикт - человек играющий?
Для психического здоровья самая большая опасность компьютерных игр заключается в возникновении зависимости. Компьютерные игры, особенно ролевые, являются одним из способов так называемой "аддиктивной реализации".
Симптомы аутизма
Симптомы аутизма на примере фильма «Человек дождя»: Явление персеверации: В течение фильма Раймонд повторял один и тот же отрывок из фильма, причём этот отрывок в фильме был шуткой, а герой, не понимая, что это шутка, просто повторял его без выразительной интонации, т.е. не было экспрессивности.
Метафора
І. Чи існують які-небудь критерії для виділення метафор? Як ми визнаемо метафору? Чи можна точно передати зміст метафори іншими словами? Що є спільне між метафорою та порівнянням?
Подарок своими руками
ВВЕДЕНИЕ Подумать только, давным-давно, много лет назад люди не праздновали день рождении! И не смогли бы отпраздновать, даже если бы захотели. Люди не умели считать дни в году. Календаря не было. А появился он благодаря древним египтянам. Мудрецы этой страны наблюдали за звездами и изучали небо и однажды изобрели Календарь.
Доказательство теоремы Ферма для n=3
Доказательство великой теоремы Ферма для n=3 методами элементарной алгебры с использованием метода решения параметрических уравнений. Диофантово уравнение, решение в целых числах, отсутствие решения в целых положительных числах при показателе степени n=3.
Контрольная работа по Математике 3
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНСТИТУТДИСТАНЦИОННОГО ОБРАЗОВАНИЯ Кафедра «Бухгалтерский учет, анализ и аудит»
Шпора по ТВИМС
Подбр.2 игральных кости. Найти вер-ть соб-й: 3 белых шара и 2 черных. Найти вер-ть Из колоды карт в 36 шт. достается 4 карты. Из ящика, содержащего 5 бел,2 черн,3 красн,
Контрольная работа
385. Вычислить несобственные интегралы или установить их расходимость. По определению несобственного интеграла имеем: Интеграл сходится. 301. Найти неопределенный интеграл.
Интеграл дифференциального уравнения
Проверка непрерывности заданных функций. Интегрирование заданного уравнения и выполние преобразования с ним. Интегрирование однородного дифференциального уравнения. Решение линейного дифференциального уравнения. Общее решение неоднородного уравнения.
Мой любимый предмет - математика сочинение-рассуждение
Автор: Сочинения на свободную тему Я часто думаю, что было бы, если бы мы до сих пор не умели писать и считать. Наверное, жизнь была бы очень скучной и однообразной. Например, я очень люблю головоломки, разные математические задачи. Они помогают мне развиваться, и я всегда радуюсь, когда нахожу правильное решение.
Льюис Керрол
Тема: Льюис Кэррол Раздел: Литература Назначение: реферат Формат: WinWord Автор: Татарович Владимир Евгеньевич frost@skamsk Использование: 2000, Соликамский Государственный Педагогический Институт, Иностранные языки, Витенберг, полученная оценка (для сочинений: год сдачи, номер школы, фамилия преподавателя, отлично
Курт Воннегут. Колыбель для кошки
«Можете звать меня Ионой» — такой фразой открывается роман. Герой-повествователь считает, что именно это имя куда более подходит ему, чем данное при рождении, ибо его «всегда куда-то заносит».
Расчёт цепей на переходные процессы
Расчёт и исследование электрических цепей при переходных процессах: до коммутации; установившийся режим; переходной процесс; график. Особенности применения классического и операторного метода при решении задач. Вид характерного уравнения с неизвестным.
Ранний железный век
Железный век – третий после каменного и бронзового веков крупный археологический период. Его первая стадия получила название . Так была названа важнейшая эпоха в истории человечества, начало которой совпадает с началом широкого применения этого металла. С начала I тыс. до н. э. вплоть до настоящего времени железо является основой материальной культуры всего человечества.
Фурман против Джорджии
Введение 1 Обстоятельства 2 Разбирательство 2.1 Решение 2.2 Мнения судей Список литературы Фурман против Джорджии Введение Фурман против штата Джорджия 408 U.S. 238 (1972) — решение Верховного суда США, установившее фактический мораторий на смертную казнь на всей территории Соединённых Штатов вплоть до принятия решения по делу Грегг против Джорджии.
Введение в проблему искусственного интеллекта
Введение в проблем у искусственного интеллекта Понятие систем ИИ, их классификация области применения и перспективы развития. ИИ - это научно-исследовательское направление создающие модели и соответствующие программные средства, позволяющие с помощью ЭВМ решать задачи творческого, не вычислительного характера, которые в процессе решения требуют обращения к семантике (проблеме смысла).
Задача Y пентамино
Введение Широкое распространение идей структурного программирования в последние 20-30 лет оказало большое влияние на теорию и практику программирования и привело к пересмотру роли типа и структуры данных при разработке соответствующих алгоритмов и программ. В связи с этим в последние десятилетия при производстве сложных программных систем требуется подготовка высококвалифицированных специалистов, в совершенстве владеющих современной теорией построения систем обработки данных.
Будда
Гаутама Будда, чье первоначальное имя было принц Сиддхартха Гаутама, был основателем буддизма, одной из величайших религий мира.
Шеннон Клод Элвуд
Клод Элвуд Шеннон (Shannon) (1916 — 2001) — американский инженер и математик. Человек, которого называют отцом современных теорий информации и связи.
Виховання інтересу до вивчення світової літератури
ВИХОВАННЯ ІНТЕРЕСУ ДО ВИВЧЕННЯ СВІТОВОЇ ЛІТЕРАТУРИ. Уроки світової літератури мають великий виховний потенціал. Саме цей курс дав можливість прилучити учнів до фундаментальних цінностей слов’янського та західного світу. Першим етапом роботи на уроці світової літератури є пробудження цікавості до читання.