Инструменты пользователя
msx:basic_dialogue_programming_language:files:diff_012
Глава XII
@@ -1,16 +1,14 @@ -c1E +\/d ГЛАВА XII. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ПОВЫШЕННОЙ ТРУДНОСТИ +\/d- - Experimentia est optima rerum magastra! - Латинская пословица Программированию нельзя научить при помощи выполняемых под команду массовых вольных упражнений... В нем нужно упражняться инди- видуально, как в хождении на лыжах и вожде- нии автомобиля. - Ф.Л.Бауэр,Р.Гнац,У.Хилл - + Ф.Бауэр,Р.Гнац,У.Хилл Преподавание программирования - дело почти безнадежное, а его изучение - непосильный труд. Преподаватель может всячески возиться со студентами, @@ -55,13 +53,11 @@ постепенно приобретает качества, необходимые программисту. Академик А.П.Ершов говорил, что "программист должен обладать способно- стью первоклассного математика к абстрактному и логическому мышлению, в -сочетании с эдисоновским талантом соорудить все, что угодно из нуля и еди- +сочетании с эдисоновским талантом соорудить все что угодно из нуля и еди- ницы. Он должен сочетать аккуратность бухгалтера с проницательностью раз- ведчика, фантазию автора детективных романов с трезвой практичностью эко- номиста. А кроме того, программист должен иметь вкус к коллективной рабо- те, понимать интересы пользователя и многое другое". - - XII.1. ЗАДАЧИ Задачи 12-40 представляют собою задачи "со звездочкой" из школьного @@ -70,7 +66,7 @@ MSX-BASIC. Часть из них использует алгоритмы, приведенные в [41,42,43]. З а д а ч а 12. Дан целочисленный массив A[N]. Проверьте,есть ли в нем - ────────────── элементы, равные нулю. Если есть,найдите номер первого + ────────────── элементы равные нулю. Если есть, найдите номер первого из них, т.е. наименьшее I, при котором A[I]=0. NEW Ok @@ -318,14 +314,11 @@ 170 FOR J=1 TO M:PRINT L(I,J);:NEXT J 180 RETURN - Аналогичный случай был ... Бравый солдат Швейк - - З а д а ч а 21. Дан двухмерный целочисленный массив A(M,N). Найти наи- ────────────── большее целое число K, обладающее таким свойством: в -любой строке таблицы есть элемент, больший или равный K. +любой строке таблицы есть элемент больший или равный K. NEW Ok 7 CLS @@ -358,13 +351,10 @@ 620 NEXT:PRINT S;"=";W$ 630 END - Совершенные числа красивы. Но известно, что красивые вещи редки и немногочисленны, без- образные же встречаются в изобилии. Никомах из Герасы (ок. 100 н.э.) - - З а д а ч а 23. Натуральное число называют с о в е р ш е н н ы м , ес- ────────────── ли оно равно сумме всех своих делителей, не считая его самого (например, 6=1+2+3 - совершенное число). Напишите алгоритм, прове- @@ -374,8 +364,9 @@ 100 INPUT"Введите натуральное N:";N:IF N=1 THEN 140 120 FOR J=1 TO N-1 130 IF N/J=FIX(N/J) THEN K=K+J:NEXT J:ELSE NEXT J - 140 IF K=N THEN PRINT N"-совершенное число" ELSE PRINT N"не является с - овершенным" + 140 IF K=N THEN PRINT N"-совершенное число" ELSE PRINT N" Не является + совершенным..." + З а д а ч а 23∗. Написать программу, находящую все совершенные числа, ─────────────── принадлежащие отрезку [1,N]. @@ -395,6 +386,7 @@ 496 Ok + З а д а ч а 24. Напечатайте в порядке возрастания первые 1000 чисел,ко- ────────────── торые не имеют простых делителей,кроме 2,3 и 5.(Начало списка: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,...). @@ -440,20 +432,20 @@ 60 FOR I=1 TO N-1 STEP 2 70 IF A(I)<A(I+1) THEN R=A(I):D=A(I+1) ELSE R=A(I+1):D=A(I) 80 G=G+1:PRINT" Итак, "G"-ОЕ ВЗВEШИВАНИЕ":PRINT - 90 PRINT" Вес "I"-ой монеты -"A(I)" граммов "I+1"-ой монет + 90 PRINT" Вес "I"- й монеты -"A(I)" граммов "I+1"- й монет ы- "A(I+1)" граммов ":PRINT 100 PRINT" Самая меньшая по весу из предыдущих монет -"R1" граммо в":PRINT 110 G=G+1:IF R<R1 THEN R1=R 120 PRINT" Меньшая из 2 только что взятых монет-"R"граммов; после сравнения этих монет ОСТАЕТСЯ монета весом "R1"граммов":PRINT - 125 PRINT " ("G"-ОЕ ВЗВЕШИВАНИЕ)":PRINT + 125 PRINT " ("G"- Е ВЗВЕШИВАНИЕ)":PRINT 130 PRINT" Самая большая по весу из предыдущих монет -"D1" граммо в":PRINT 140 G=G+1:IF D>D1 THEN D1=D 150 PRINT" Большая из 2 только что взятых монет-"D"граммов; после сравнения этих монет ОСТАЕТСЯ монета весом "D1" граммов":PRINT - 155 PRINT " ("G"-OE ВЗВЕШИВАНИЕ)":PRINT + 155 PRINT " ("G"- E ВЗВЕШИВАНИЕ)":PRINT 160 H$=INPUT$(1):GOSUB 200 170 C=C+3:NEXT I 180 PRINT:PRINT"После долгих стараний: ("C" взвешиваний) мы наш @@ -490,7 +482,7 @@ 100·N взвешиваний на чашечных весах без гирь. 5 'Автор программы: Шарковский Игорь (9 класс), 02.01.90 10 KEY OFF:CLS:COLOR 15,4 - 20 INPUT"Количество монет (нечетное число, не большее 13)";N + 20 INPUT"Количество монет (нечетное число не большее 13)";N 30 IF N/2=FIX(N/2) OR N>13 THEN CLS :RUN20 ELSE X=RND(-TIME):DIM A(N) 40 PRINT "В вашем кошельке лежат монеты:" 50 FOR I=1 TO N:PRINT "┌────┐";:NEXT:PRINT: @@ -514,11 +506,12 @@ по массе)":FOR I=1 TO 1000:NEXT:PRINT 190 PRINT "Средняя по массе монета в Вашем кошельке -"A(FIX(N/2)+1)"г" :PRINT"Число взвешиваний -"K :FOR I=1 TO 1000:NEXT - 220 LOCATE 4+FIX(N/2-1)*6,11:PRINT " ▁▄▇▄▁" - 230 LOCATE 4+FIX(N/2-1)*6,12:PRINT " ▊▊▊" + 220 LOCATE 4+FIX(N/2-1)*6,11:PRINT " ▲ " + 230 LOCATE 4+FIX(N/2-1)*6,12:PRINT " │ " 235 LOCATE 4+FIX(N/2-1)*6,13:PRINT " ВОТ ОНА" 240 LOCATE 0,24 + З а д а ч а 28. Последовательность A(1),A(2),A(3),... определяется так ────────────── А(1)=1, A(2N)=A(N), A(2N+1)=A(N)+A(N+1). Напишите программу, вычисляющую A(N) по известному N. @@ -530,11 +523,8 @@ 520 PRINT A(I);:NEXT:PRINT:PRINT "An=";A(N) 530 END - Каждая истинная работа имеет свою красоту. - Н.К.Рерих - - + Н.Рерих З а д а ч а 29. Дан целочисленный массив A(N).Найдите наименьшее число ────────────── К элементов, которые нужно "выкинуть" из последователь- ности A(1),A(2),...,A(N), чтобы осталась возрастающая последовательность. @@ -567,9 +557,8 @@ примеров без утомительного набора их на клавиатуре. Строки с 30 по 100 по- зволяют с помощью дополнительного массива Q найти наименьшее число K эле- ментов, которые нужно "выкинуть" из массива, чтобы осталась возрастающая -подпоследовательность. И, наконец, в строках 120-140 происходит выделение +подпоследовательность. И наконец, в строках 120-140 происходит выделение этой максимальной по длине подпоследовательности. - З а д а ч а 30. Дано три целочисленных массива A(N), B(N), C(N). Из- ────────────── вестно, что существуют целые числа, встречающиеся во всех трех таблицах. Найдите одно из таких чисел. @@ -649,8 +638,7 @@ 160 IF D=0 THEN:::IF C=0 THEN PRINT "Неопределенность":END ELSE PRINT" Нет решения":END:::ELSE 170 IF FIX(C/D)*D<>C THEN PRINT "Нет решения":END - 180 A=A/D:B=B/D:C=C/D 'Уравнение приведем к виду, когда A и B взаимно - простые. + 180 A=A/D:B=B/D:C=C/D 'A и B сделаем взаимно простыми 190 IF N=0 THEN V=0:U=1 ELSE V=1:U=0:::FOR I=N-1 TO 1 STEP -1:S=V:V=U -V*Q[I]:U=S:NEXT I 200 X=C*U*SGN(A):Y=C*V*SGN(B):C=FIX(X/B):X=X-C*B:Y=Y+C*A'Частные решен @@ -672,11 +660,9 @@ 330 '│ 10 │ 12 │ 97 │ Нет решения │ 340 '└───────────────────────────────┘ - А вы, друзья, как не садитесь, + А вы, друзья, как ни садитесь, Все в музыканты не годитесь. - И.А.Крылов - - + И.Крылов З а д а ч а 33. Перестановкой N чисел называется последовательность ────────────── A(1),A(2),...,A(N), в которой встречаются по одному разу все числа от 1 до N. (Например, перестановками трех чисел являются: @@ -691,16 +677,15 @@ ния всех перестановок (без повторений). Некоторые из этих незаслуженно за- бытых методов были переоткрыты в настоящее время в связи с появлением циф- ровых машин. Это искусство просуществовало до наших дней, поскольку знаме- -нитая "Книга рекордов Гиннеса" содержит упоминание о выбивании всех +нитая Книга рекордов Гиннеса содержит упоминание о выбивании всех 8!=40320 перестановок на 8 колоколах в 1963 году;установление этого рекор- да потребовало 17 часов 58.5 минут! Конечно, использование цифровых машин позволяет генерировать перестановки значительно быстрее,однако разница не так уж велика, как можно было бы подумать - за 18 часов даже самый быст- рый компьютер не сможет получить все перестановки n-элементного множества, если n>13 (с другой стороны, перестановки 8-элементного множества можно -получить в течении доли секунды). Это простое следствие того факта,что n! +получить в течение доли секунды). Это простое следствие того факта,что n! растет весьма быстро с ростом n. - Укажем алгоритм получения всех перестановок из N элементов. Пусть имеется множество элементов A={A ,A ,...,A }. Обозначим две разные 1 2 N @@ -708,7 +693,6 @@ i i i j j j А =[A ,A ,...,A ] и A =[A ,A ,...,A ] . i 1 2 N j 1 2 N - Определение. Две перестановки называются у п о р я д о ч е н н ы м и ─────────── в л е к с и к о г р а ф и ч е с к о м смысле, A >A , если: @@ -720,14 +704,12 @@ i j i j A =A для всех l из [1,k-1] и A >A . l l k k - П р и м е р 1. Пусть A={1,2,3,4};A =[4,3,2,1];A =[4,2,1,3]. ───────────── i j Перестановки A и A упорядочены лексикографически, A >A ,так как выполня- i j i j i j i j ются условия A =A и А >A . 1 1 2 2 - П р и м е р 2. Лексикографически упорядочены фамилии владельцев телефо- ───────────── нов в телефонном справочнике. Таким образом, если мы научимся генерировать перестановки в лексикогра- @@ -735,7 +717,7 @@ "самой маленькой" и кончая "самой большой". Пусть исходное множество, для которого нужно получить все перестанов- ки, есть множество натуральных чисел 1,2,...,N. Положим, что исходная пе- -рестановка 1,2,...N. Текущую перестановку обозначим +рестановка - 1,2,...N. Текущую перестановку обозначим A=[A ,A ,...,A ] . 1 2 N Предлагается следующая последовательность действий (можно доказать,что @@ -788,7 +770,6 @@ Кстати, какие изменения нужно внести в программу,чтобы она строила все перестановки множества букв латинского алфавита? Может ли она проделать те же преобразования с буквами русского алфавита? - З а д а ч а. Написать все предложения,которые можно составить из слов ─────────── "Ваши прекрасные глаза", "прекрасная маркиза","от любви", "сулят", "мне", "смерть" путем их всевозможных перестановок (данная ситу- @@ -873,7 +854,7 @@ 10 CLS:INPUT"Число городов";N 20 DIM CC[N,N],ST[N,N],G[N] 30 FOR I=1 TO N:FOR J=1 TO N - 40 PRINT"Из"I"-го города в"J"-ый:";:INPUT CC[I,J] + 40 PRINT"Из"I"-го города в"J"- й:";:INPUT CC[I,J] 50 NEXT J,I 60 PRINT"Это - данная таблица:" 70 FOR I=1 TO N:FOR J=1 TO N:PRINTCC[I,J];TAB(4*J);:NEXTJ:PRINT:NEXTI @@ -895,14 +876,11 @@ 220 FOR I=1 TO N:FOR J=1 TO N 'Вывод таблицы цен 230 PRINT ST[I,J];TAB(4*J);:NEXT J:PRINT:NEXT I - Вся шахматная партия - это один замаски- рованный ход конем. С.Тартаковер Трава не растет там,где ступил мой конь. Аттила - вождь гуннов - - З а д а ч а 37. Существует способ обойти шахматным конем шахматную ────────────── доску, побывав на каждом поле по одному разу. Составь- те алгоритм отыскания такого способа. @@ -1120,15 +1098,18 @@ 5,1,25,25,25,25,25,1,1,254 + + + + + Если в задаче меньше трех переменных, это не задача; если больше восьми - она неразрешима. Закон Мэрфи - - З а д а ч а 38. Существуют способы расстановки 8 ферзей на шахматной - ────────────── доске так, чтобы они не били друг друга. Составьте ал- -горитм, отыскивающий один из таких способов. + ────────────── доске такие, что они не бьют друг друга. Составьте ал- +горитм, отыскивающий хотя бы один из них. NEW Ok 10 'Расстановка 8 ферзей. Минимальное время работы - 14 минут. @@ -1206,6 +1187,10 @@ 570 PUT SPRITE 8,(20*N8+2,20*8+2),8,1 580 RETURN + + + + З а д а ч а 39. Некоторые натуральные числа могут быть представлены в ────────────── виде суммы кубов целых неотрицательных чисел: например, 9=2^3+1^3, 27=3^3+0^3. Составьте алгоритм, отыскивающий наименьшее нату- @@ -1232,6 +1217,8 @@ 1729=10^3+9^3 Ok + + З а д а ч а 40. Составьте алгоритм, вычисляющий по заданным веществен- ────────────── ным числам A, B, C, D величины A·C+B·D и A·D-B·C. Этот алгоритм может использовать промежуточные величины, операции сложения, вы- @@ -1272,8 +1259,8 @@ NEW Ok 22 CLS:PRINT:PRINT:INPUT"Число М ";M:DIM A$(17) - 50 FOR I=1 TO 4:FOR J=1 TO 4:FOR K=1 TO 4:FOR L=1 TO 4:FOR N=1 TO 4:FO - R S=1 TO 4:FOR P=1 TO 4:FOR R=1 TO 4:A=1 + 50 FOR I=1 TO 4: FOR J=1 TO 4: FOR K=1 TO 4: FOR L=1 TO 4: + FOR N=1 TO 4: FOR S=1 TO 4: FOR P=1 TO 4: FOR R=1 TO 4: A=1 70 IF I=1 THEN A=A+2:A$(2)="+" ' ∗∗∗ В строках 70-390 осуществляется 80 IF I=2 THEN A=A-2:A$(2)="-" ' полный перебор возможных комбинаций 90 IF I=3 THEN A=A*2:A$(2)="*" ' расположения символов +,-,*,/ меж- @@ -1309,7 +1296,7 @@ 390 IF A=M THEN G=G+1:GOTO 420 395 LOCATE 16,7:PRINTI;J;K;L;N;S;P;R; 400 NEXT R,P,S,N,L,K,J,I - 410 IF W<>=4THENPRINT"УВЫ......":END ELSE END + 410 IF W=4 THEN PRINT "УВЫ...": END ELSE END 420 FOR Y=1 TO 17 STEP 2:A$(Y)=STR$((Y+1)/2):NEXTY 430 LOCATE0,10+G:FOR Y=1 TO 17 440 PRINTA$(Y);:NEXT Y @@ -1322,11 +1309,10 @@ 1 + 2 + 3 * 4 + 5 + 6 - 7 + 8 + 9 ··· Ok - З а д а ч а 43. Составить программу, определяющую количество "счастли- ────────────── вых" автобусных билетов (номер билета шестиразрядный). -Билет считается "счастливым", если сумма трех старших цифр его номера со- -впадает с суммой трех младших цифр. +Билет считается "счастливым", если сумма трех первых цифр его номера со- +впадает с суммой трех последних цифр. П е р в ы й способ. В т о р о й способ. 10 INPUT N,M 10 TIME=0:DIM A%(27) 20 FOR T=INT(N/1000) TO INT(M/1000) 20 FOR I=0 TO 9:FOR J=0 TO 9:FOR @@ -1453,11 +1439,9 @@ Что наша "Жизнь"? Игра! М.Гарднер - - З а д а ч а 46. Написать программу, реализующую на текстовом экране ────────────── алгоритм игры "Жизнь". - Игра "Жизнь" придумана сотрудником Кембриджского универитета Дж. Конве- + Игра "Жизнь" придумана сотрудником Кембриджского университета Дж.Конве- ем. "Жизнь" - многоклеточное сообщество, населяющее пустыню, которая пред- ставляет собой прямоугольную решетку, каждая ячейка которой вмещает одну клетку Жизни. Мерой течения времени служит смена поколений Жизни, принося- @@ -1552,14 +1536,13 @@ 1 2 n заменяя каждую левую скобку на 1, и каждую правую скобку - на -1.Этот мас- сив назовем и з о б р а ж е н и е м слова A. Имеет место следующая - Т е о р е м а. Массив A , A ,..., A , где A =±1 , i=1, 2,..., n ───────────── 1 2 n i является изображением правильного скобочного выражения тогда и только тог- да, когда α) A =1; 1 k - β) для каждого k такого, что 1<k<n, выполнено ∑ A ≥ 0; + β) для каждого k такого что 1<k<n, выполнено ∑ A ≥ 0; i=1 i n γ) ∑ A = 0. @@ -1578,7 +1561,7 @@ ное зерно возвращается в банку, а если они разного цвета, то в банку воз- вращается белое зерно. Требуется при помощи компьютера качественно описать множества белых и -черных зерен, первоначально находившихся в банке, при условии, что послед- +черных зерен, первоначально находившихся в банке, при условии что послед- нее зерно, оставшееся в банке - черное (соответственно - белое). NEW Ok @@ -1609,13 +1592,11 @@ XII.2. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ - Один человек купил трех коз и заплатил 3 рубля. Спрашивается: по чему каждая коза пошла? Старинная задача-шутка (конец ХVI века) - 1. Для запоминания числа π иногда используют "магические" фразы, напри- мер:"это я знаю и помню прекрасно пи многие знаки мне лишни напрасны" или "кто и шутя и скоро пожелаетъ пи узнать число ужъ знаетъ". Число букв в @@ -1645,13 +1626,13 @@ совпадают, то игра не закончена. Ведущий сообщает игроку количество "бы- ков" и "коров", содержащихся в предложенном им пробном числе. "Быками" на- зывают те его цифры, которые по значению и позиции совпадают с соответст- -вующимий цифрами задуманного кода. В нашем примере "бык" один - цифра 8. +вующими цифрами задуманного кода. В нашем примере "бык" один - цифра 8. "Коровы" - это цифры, которые совпадают с цифрами задуманного кода, но на- ходятся в иных позициях. В числе 7984 "коров" две: 9 и 4. Понятно, что от- гадать код или назвать четыре "быка" - это одно и тоже. 4. Написать программу определения соответствующего дня недели по извест- -ным целым числам: J - число, М - месяц, А - год,применяя метод Ленуара М., +ным целым числам: J - число, М - месяц, А - год,применяя метод М.Ленуара, который заключается в следующем: 1) вычислить величину N: если месяц - январь или февраль високосного года, то N=1; @@ -1665,18 +1646,15 @@ 2) вычислить "код" дня С по формуле: С=[365.25·А2]+[30.56·М]+J+N; 3) вычислить остаток S от деления С на 7: - если S=0, то день - среда,если S=1, то день - четверг, если S=2, то - день - пятница,..., если S=6, то день - вторник. - + если S=0, то день - среда; если S=1, то день - четверг; если S=2, + то день - пятница,...; если S=6, то день - вторник. Незатейливые головоломки о целых числах веками служили источником обновления ма- тематики. - Г.Д.Биркгоф - - + Г.Биркгоф 5. Гольдбахом было высказано предположение, что каждое четное число, -большее или равное 4, представимо в виде суммы двух простых. +большее или равное 4 представимо в виде суммы двух простых. Это предположение до сих пор не доказано и не опровергнуто. Написать программу проверки этой гипотезы для данного четного числа. Результатом выполнения программы должен быть вывод самого числа,если не удалось найти @@ -1685,12 +1663,12 @@ 6. Составить программу поиска среди чисел n, n+1, ..., 2n так называ- емых б л и з н е ц о в, т.е. двух простых чисел,разность которых равна 2. -Если близнецы в указанном диапазоне найдены, то вывести 1, если близнецов +Если близнецы в указанном диапазоне найдены, то вывести 1; если близнецов нет, то вывести 0. 7. Написать игровую программу "Игры на дорожке". Суть ее в том,что два противника двигают фишки, находящиеся на противоположных сторонах дорожки, -разбитой на n полей, например,на одной из вертикалей шахматной доски, где +разбитой на n полей, например на одной из вертикалей шахматной доски, где дорожка содержит 8 полей. Ходы делаются поочередно.За один ход каждый уча- стник может подвинуть свою фишку не более чем на m полей вперед или назад. При этом нельзя перепрыгивать через фишку партнера и покидать пределы до- @@ -1704,6 +1682,7 @@ где: [] - символ выделения целой части, α - искомый показатель, l=[lg(n)/lg(p)]. Например, если n=367, p=3, то α=180. + З а м е ч а н и е. Так можно разложить n! на простые множители,беря за p последовательно все простые числа, меньшие n . @@ -1748,15 +1727,13 @@ Вторая дружественная пара (1184 и 1210) была найдена в 1867 году шест- надцатилетним итальянцем Б. Паганини. Написать программу для нахождения дружественных чисел, используя спо- -соб, указанный еще в 9-м веке арабским математиком Сабитом ибн Корра. - +соб, указанный еще в IX в. арабским математиком Сабитом ибн Корра. Т е о р е м а С а б и т а . Если все три числа n-1 2n-1 p=3·2 -1 , q=3·2ⁿ-1 , r=9·2 -1 - простые, то числа A=2ⁿpq и B=2ⁿr - дружественные. - При n=2 числа p=5, q=11 и p=71 - простые, и получается пара чисел 220 -и 284, найденная еще Пифагором. Однако, теорема Сабита дает дружественные +и 284, найденная еще Пифагором. Однако теорема Сабита дает дружественные числа и при других n, например: n=4 n=7 А=17296 А=9363584 @@ -1787,7 +1764,16 @@ ветствующие числа a , a ,..., a . s s-1 0 + 16. Известно, что если наудачу выписаны два натуральных числа, то веро- +ятность того, что они взаимно просты, равна 6/π² (задача П.Л.Чебышева). + Используя этот результат, вычислить число π. + + 17. Вычислить √ 1+2·√ 1+3·√ 1+4·√ 1+··· + Выдающийся индийский математик Рамануджан доказал, что результат равен +трем. + Наконец, отметим, что очень много интересных и сложных задач приведено в книге С.А.Абрамова, Г.Г.Гнездилова, Е.Н.Капустина, М.И.Селюна "Задачи -по программированию". М.:Наука,1988. +по программированию" (М.:Наука,1988). +
msx/basic_dialogue_programming_language/files/diff_012.txt · Последние изменения: 2022-10-01 13:59 — GreyWolf
Инструменты страницы
Если не указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution-Noncommercial-Share Alike 4.0 International
