Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Решение головоломки Ж. Арсака

Название: Решение головоломки Ж. Арсака
Раздел: Рефераты по информатике, программированию
Тип: реферат Добавлен 06:30:05 28 февраля 2008 Похожие работы
Просмотров: 50 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений22:32:27 18 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
15:56:30 24 ноября 2015

Работы, похожие на Реферат: Решение головоломки Ж. Арсака

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(149934)
Комментарии (1829)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru