Скачать Решение головоломки Ж. Арсака

Выполнила ученица 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г.

Для подготовки данной работы были использованы материалы с сайта http://licey43.ru




Получить работу.

Похожие работы:

Философия Возрождения о Человеке и Боге
(Ренессанс: от Бога к Человеку; от Человека-Бога к Богу –Миру; от обожествления Человека к омирщению Космоса) Учебное пособие Аннотация Это пособие было написано в 1992-1993 гг. в рамках конкурса «Гуманитарное образование в высшей школе». Фонд Сороса профинансировал исследовательскую часть работы, ее апробацию, но не нашел денег для публикации.


CАМООРГАНИЗАЦИЯ В РЕФОРМЕ ВУЗОВСКОГО ФИЗИЧЕСКОГО ВОСПИТАНИЯ
Мы вступили в эру, которая призывает нас к уравновешенности в общественном устройстве, к сбалансированности в отношениях с окружающей средой, к достижению гармонии и внутреннему равновесию в каждом из нас. Осуществление поворота от материального прогресса к духовному человеку, к личности как главному созидательному мотиву человеческой деятельности - важнейшая глобальная проблема современности, разрешение которой способно снова наполнить смыслом нашу индивидуальную и личную жизнь, до сих пор придавленную излишним стремлением к материальной пользе [1].


Русский модернизм - Контрольная работа

Категория: Культура и искусство
Предмет:Искусство модернизма
Вид работы: Контрольная работа
Дата сдачи:01.04.2009
Язык: русский
Описание: Многообразие художественных и социальных форм модернизма. Генезис предпосылок русского модерна. Анализ национально-романтических тенденций в русском модерне. Попытки создания синтетических форм искусства. Многочисленные модернистские направления.


Организация, производительность и оплата труда.


Система налогов и сборов в РФ - Контрольная работа
Категория: Финансы, деньги и налоги
Предмет:Налоговое право
Вид работы: Контрольная работа
Дата сдачи:28.02.2010
Язык: русский
Описание: Предмет налогового права, метод правового регулирования. Объект налогообложения, реализация товаров, работ. Взыскание налога, пени за счет денежных средств находящихся на счетах налогоплательщика. Обеспечение исполнения обязанностей по уплате налогов.


Юридическая природа решений Конституционного Суда Российской Федерации, проблемы их исполнения - Курсовая работа
Категория: Государство и право
Предмет:Конституционное право РФ
Вид работы: Курсовая работа
Дата сдачи:25.02.2010
Язык: русский
Описание: Конституционный суд Российской Федерации - высшая судебная инстанция России: его место в системе органов судебной власти. Полномочия, структура и организация Конституционного суда. Механизм принятия и юридическая сила решений, проблема их исполнения.




Темы последних работ:
Работа "Решение головоломки Ж. Арсака" была сдана на отлично.

Чтобы оценить материал, вам необходимо зарегистрироваться
Только зарегистрированные пользователи могут оставлять комментарии


Комментариев: 0


Подписка

Введите свой e-mail:

Система налогов и сборов в РФ - Контрольная работаАнализ имущественного положения предприятия и оценка эффективности использования его активовЛуи Себастьян Мерсье. 2440 годГлава государства - Курсовая работаСлавянская община - РефератАнестезия при хирургических вмешательствах в трудных условиях - РефератЛандшафтна екологія - Курсовая работа Практика рассмотрения дел с участием таможенных органов - Реферат

Сайт создан в системе uCoz