\/d ГЛАВА XII. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ПОВЫШЕННОЙ ТРУДНОСТИ \/d- Программированию нельзя научить при помощи выполняемых под команду массовых вольных упражнений... В нем нужно упражняться инди- видуально, как в хождении на лыжах и вожде- нии автомобиля. Ф.Бауэр,Р.Гнац,У.Хилл Преподавание программирования - дело почти безнадежное, а его изучение - непосильный труд. Преподаватель может всячески возиться со студентами, читать лекции, делать критические замечания, направлять по верному пути. Студент может все тщательно записывать, запоминать, читать, сдавать заче- ты, дискутировать хоть до двух ночи. ┌──────────────────────────────────────────────────────────┐ │ Но все усилия т щ е т н ы , если студент │ │ не будет п р а к т и к о в а т ь с я в написании │ │ п р о г р а м м , │ │ поскольку навык программирования дается │ │ т о л ь к о п р а к т и к о й. │ └──────────────────────────────────────────────────────────┘ Более того, учиться надо на "настоящих" программах, а не на упрощенных примерах, вроде тех, которыми изобилует большинство руководств по языкам программирования. Перечислим те способности, которые жизненно необходимы в с я к о м у п р о г р а м м и с т у [17]. 1. Способность читать и понимать описание поставленной задачи, улавли- вать пожелания того, кто ее ставит (что не всегда легко, так как и задачи, и те, кто их ставит, часто отличаются именно неуловимостью).Учтите третий закон Чизхолма:"Любую цель люди понимают иначе,чем человек, ее указующий". 2. Способность четко видеть действительные трудности и отбрасывать все, не относящееся к делу. 3. Способность выявить все случаи, где можно применить теорию, самосто- ятельно решиться на ее применение или обратиться за советом к специалисту. 4. Способность разбить задачу на ряд обозримых независимых частей и по- нять взаимосвязи этих частей. 5. Способность оценивать эффективность предлагаемых решений с точки зрения затрат на программирование, машинных ресурсов и удовлетворения по- требностей пользователя и находить приемлемый компромисс между этими вида- ми эффективности. 6. Способность объединять множество частных решений воедино, получая при этом четкое и изящное решение всей задачи. 7. Способность выражать решения на простом и понятном языке. Естествен- ный это язык или искусственный - роли не играет, важно лишь,чтобы правиль- ность решения была ясна и людям, и компьютеру. 8. И наконец,способность при неудаче подавить самолюбие и поискать дру- гой подход (или даже другую задачу). Способности эти, как видим, столь сложны и многообразны, что приобрес- ти их можно т о л ь к о на п р а к т и к е. Накапливая опыт, студент постепенно приобретает качества, необходимые программисту. Академик А.П.Ершов говорил, что "программист должен обладать способно- стью первоклассного математика к абстрактному и логическому мышлению, в сочетании с эдисоновским талантом соорудить все что угодно из нуля и еди- ницы. Он должен сочетать аккуратность бухгалтера с проницательностью раз- ведчика, фантазию автора детективных романов с трезвой практичностью эко- номиста. А кроме того, программист должен иметь вкус к коллективной рабо- те, понимать интересы пользователя и многое другое". XII.1. ЗАДАЧИ Задачи 12-40 представляют собою задачи "со звездочкой" из школьного учебника [11]. Остальные задачи (41-48) - это задачи олимпиадного типа по информатике. Программы составлены на диалоговом языке программирования MSX-BASIC. Часть из них использует алгоритмы, приведенные в [41,42,43]. З а д а ч а 12. Дан целочисленный массив A[N]. Проверьте,есть ли в нем ────────────── элементы равные нулю. Если есть, найдите номер первого из них, т.е. наименьшее I, при котором A[I]=0. NEW Ok 10 DEFINT A-Z:INPUT N:IF N<=0 THEN CLS:GOTO 10 ELSE DIM A(N) 20 FOR I=1 TO N:A(I)=INT(2*RND(-TIME)):PRINT A(I);:NEXT:PRINT 30 FOR I=1 TO N:IF A(I)=0 THEN PRINT"Первый нулевой элемент:";I:END EL SE NEXTI:PRINT "Нулевого элемента нет!":END З а д а ч а 13. Дан целочисленный массив A[N]. Проверьте, есть ли в ────────────── нем отрицательные элементы. Если есть,найдите наиболь- шее I, при котором A[I]<0. NEW Ok 10 INPUT N:DIM A(N):FOR I=1 TO N:A(I)=INT(2*RND(-TIME)-1):PRINT A(I);: NEXT I:PRINT 20 FOR I=1 TO N:IF A(I)<0 THEN B=I:NEXT I ELSE NEXT I 30 IF B=0 THEN PRINT"Отрицательного элемента в массиве нет" ELSE PRINT "Номер последнего отрицательного элемента:";B З а д а ч а 14. Проверьте, образуют ли элементы двухмерного массива ────────────── A[N,N] "магический квадрат" (это значит, что суммы чи- сел во всех ее вертикалях, всех горизонталях и двух диагоналях одинаковы). NEW Ok 10 INPUT "Сторона квадрата";N:DIM A(N,N):FOR I=1 TO N:FOR J=1 TO N:PRI NT "Ввести";J;"элемент";I;"строки";:INPUT A(I,J):NEXT J:NEXT I 20 DIM S(N):FOR I=1 TO N:FOR J=1 TO N:S(I)=S(I)+A(J,I):NEXT J:NEXT I 30 FOR I=1 TO N-1:IF S(I)<>S(I+1) THEN PRINT "Элементы массива не обра- зуют магический квадрат!":END 40 DIM C(N):FOR J=1 TO N:FOR I=1 TO N:C(J)=C(J)+A(J,I):NEXT I:NEXT J 50 FOR J=1 TO N-1:IF C(J)<>C(J+1) THEN PRINT "Элементы массива не обра- зуют магический квадрат!":END 60 Q1=0:FOR I=1 TO N:FOR J=1 TO N:IF J=I THEN Q1=Q1+A(I,J):NEXT I ELSE NEXT J:NEXT I 70 IF Q1<>C(1) THEN PRINT "Не является!":END 80 Q2=0:FOR I=N TO 1 STEP -1:FOR J=N TO 1 STEP -1:IF J=I THEN Q2=Q2+A( I,J):NEXT I ELSE NEXT J:NEXT I 90 IF Q1=Q2 THEN PRINT "Магический квадрат есть!":END З а д а ч а 14.1 Постройте "магический квадрат" нечетного порядка. ──────────────── NEW Ok 80 INPUT N:DIM S(N,N) 90 FOR I=1 TO N:FOR J=1 TO N 100 B=J-I+(N-1)\2:C=2*J-I 110 IF B>=N THEN B=B-N ELSE IF B<0 THEN B=B+N 120 IF C>N THEN C=C-N ELSE IF C<=0 THEN C=C+N 130 S(I,J)=B*N+C:NEXT J,I 140 FOR I=1 TO N:FOR J=1 TO N 150 PRINTUSING"####";S(I,J);:NEXTJ:PRINT:NEXTI З а д а ч а 14.2 Постройте "магический" квадрат четного порядка. ──────────────── NEW Ok 10 DEFINT A-Z:GOTO 120 20 FOR I=P1 TO Q1:H1=NOT H1 30 IF H1><0 THEN X[I,A1]=NN-A1*N+1+N-IELSEX[I,A1]=A1*N-N+I 40 NEXT:RETURN '──▶ 50 FOR I=P2 TO Q2:H2=NOT H2 60 IF H2><0 THEN X[I,A2]=A2*N+1-I ELSE X[I,A2]=NN-A*N+I 70 NEXT:RETURN '──▶ 80 FOR I=P3 TO Q3:H3=NOT H3 90 IFH3><0THENX[I,A3]=A3*N+1-I ELSE X[I,A3]=NN-A3*N+N-I+1 100 NEXT:RETURN '──▶ 110 '∗∗∗∗∗ Основная программа ∗∗∗∗∗ 120 INPUT N:IF N=2 THEN PRINT"Подобный квадрат Вы легко составите само стоятельно! Good luck!":END ELSE DIM X[N,N] 130 N2=N\2:NN=N*N:P=(N=(N\4)*4):Q=P::R=-1 140 FOR A=1 TO N2-1 150 P2=1:Q2=A-1:A2=A:H2=R:GOSUB 50:P1=A:Q1=N2-1:A1=A:H1=-1:GOSUB 20 160 IF Q THEN X[N2,A]=NN-A*N+N2+1 ELSE X[N2,A]=NN-A*N+N2 170 P1=N2+1:Q1=N:A1=A:H1=NOT Q:GOSUB 20:Q=NOT Q:R=NOT R:NEXT 180 P1=1:Q1=N2-1:A1=N2:H1=NOT P:GOSUB 20:P1=N2+2:Q1=N:A1=N2:H1=0:GOSUB 20 190 P3=1:Q3=N2-1:A3=N2+1:H3=P:GOSUB 80:P3=N2+2:Q3=N:A3=N2+1:H3=-1:GOSU B 80 200 Q=P:R=-1 210 FOR A=N2+2 TO N 220 P2=1:Q2=N-A:A2=A:H2=Q:GOSUB 50 230 X[N-A+1,A]=A*N-A+1 240 P2=N-A+2:Q2=N2-1:A2=A:H2=-1:GOSUB 50 250 IF NOT R THEN:::X[N2,A]=NN-A*N+N2:X[N2+1,A]=A*N-N2+1:::ELSE:::FOR B=N2 TO N2+1:X[B,A]=NN-A*N+N-B+1:NEXT B 260 P2=N2+2:Q2=A-1:A2=A:H2=NOT R:GOSUB 50:P1=A:Q1=N:A1=A:H1=-1:GOSUB20 270 Q=NOT Q:R=NOT R:NEXT A 280 FOR A=N2 TO N2+1:FOR B=N2 TO N2+1 290 IF P<>0 THEN X[B,A]=A*N-N+B ELSE X[B,A]=NN-A*N+N-B+1 300 NEXT B,A 310 IF NOT P THEN:::FOR A=N2 TO N2+1:X[N2-1,A]=A*N-N2+2:NEXT:::FOR B=N 2 TO N2+1:X[B,N2+2]=N*N2-2*N+B:NEXT 320 FOR F1=1 TO N:FOR F2=1 TO N:PRINTUSING"####";X[F1,F2];:NEXT F2:PRI NT :NEXT F1 330 END run ? 8 1 16 41 40 32 17 56 57 63 10 23 26 39 47 50 2 3 54 19 38 30 43 11 62 61 52 45 28 36 21 12 5 60 13 44 29 37 20 53 4 6 51 22 35 27 46 14 59 58 15 42 31 34 18 55 7 8 49 24 33 25 48 9 64 Ok З а д а ч а 15. Дан целочисленный массив A(N). Подсчитайте наибольшее ────────────── число одинаковых идущих в нем подряд элементов. NEW Ok 10 Z=RND(-TIME):INPUT"Число элементов";N:DIM A(N) 20 FOR T=1 TO N: A(T)=INT(2*RND(1)):PRINT A(T);: NEXT T:K=1:F=0:PRINT 30 FOR I=1 TO N-1 40 IF A(I)=A(I+1) THEN K=K+1:M=K ELSE M=K:K=1 50 IF M>F THEN F=M 60 NEXT I:PRINT"Максимальная длина:"F run Число элементов? 9 0 1 0 1 1 0 0 1 0 Максимальная длина: 2 Ok З а д а ч а 16. Подсчитайте количество различных чисел, встречающихся ────────────── в целочисленном массиве A(N).Повторяющиеся числа учиты- вайте один раз. NEW Ok 10 DEFINT N,I,Y,L:INPUT N:DIM A(N):X=RND(-TIME) 20 FOR I=1 TO N:A(I)=INT(20*RND(1)-10):PRINTA(I);:NEXT:?:IF N=1 THEN P RINT "Один-одинешенек!":END 70 FOR Y=1 TO N-1:FOR L=Y+1 TO N 80 IF A(Y)A(I+1) THEN U=U+1:NEXT I ELSE NEXT I 120 PRINT "Количество различных элементов";U З а д а ч а 17. Дан целочисленный массив A(N). Постройте массив B(N), ────────────── который состоит из тех же элементов,что и массив A,но в котором все отрицательные элементы предшествуют всем неотрицательным. NEW Ok 30 INPUT"Число элементов";N 40 DIM A(N),B(N):Z=RND(-TIME) 50 INPUT"Чему равен максимальный элемент";F 60 PRINT "Это - данная таблица:" 70 FOR I=1 TO N:A(I)=INT(2*F*RND(1)-F):PRINT A(I);:NEXT:? 80 I=1:J=1:IF I>N THEN 120 90 FOR K=1 TO 0 STEP 1 100 IF A(I)<0 THEN B(J)=A(I):J=J+1 110 I=I+1:K=(I<=N):NEXT K 120 I=1:IF I>N THEN 170 130 FOR K=1 TO 0 STEP 1 140 IF A(I)>=0 THEN B(J)=A(I):J=J+1 150 I=I+1:K=(I<=N):NEXT K 160 PRINT "А это - искомая таблица:" 170 FOR J=1 TO N:PRINT B(J);:NEXT run Число элементов? 10 Чему равен максимальный элемент? 9 Это - данная таблица: 6 -4 1 6 2 7 7 -9 -5 -5 А это - искомая таблица: -4 -9 -5 -5 6 1 6 2 7 7 Ok З а д а ч а 18. Даны целочисленные массивы A(N),B(M), причем ────────────── A(1)≤A(2)≤···≤A(N), B(1)≤B(2)≤···≤B(M). Постройте целочисленный массив C(N+M), содержащий все элементы массивов A и B, в котором C(1)≤C(2)≤···≤C(N+M) . Эта важная задача принципиально должна быть выполнена за N+M действий. Возьмем из A и B по первому элементу.Меньший из них занесем в C и заменим следующим из его же массива. Снова выберем меньший из двух, занесем в C и т.д. После каждого сравнения в C добавляется элемент - значит, сравнений будет меньше, чем N+M. Нужно только позаботиться о том,чтобы программа ра- ботала верно и при исчерпании одного из массивов. NEW Ok 10 INPUT"Введите число элементов в массиве A, затем - в массиве B";N,M: FF=RND(-TIME) 20 DIM A(N),B(M),C(N+M) 30 FOR K=1 TO N:A(K)=INT(7*RND(1)):NEXT 40 FOR L=1 TO M:B(L)=INT(9*RND(1)):NEXT 41 FOR I=1 TO N-1:FOR J=I+1 TO N:IF A(I)>A(J) THEN SWAP A(I),A(J) 42 NEXT J,I 43 FOR I=1 TO N:PRINT A(I);:NEXT:PRINT 45 FOR I=1 TO M-1:FOR J=I+1 TO M:IF B(I)>B(J) THEN SWAP B(I),B(J) 46 NEXT J,I 47 FOR I=1 TO M:PRINT B(I);:NEXT:PRINT 50 P=0:Q=0 60 FOR I=1 TO N+M 70 IF P=N THEN Q=Q+1:C(I)=B(Q):NEXT:GOTO 110 80 IF Q=M THEN P=P+1:C(I)=A(P):NEXT:GOTO 110 90 IF A(P+1)50 THEN 10 20 DIM A(N,M):G=RND(-TIME) 30 FOR I=1 TO N:FOR J=1 TO M:A(I,J)=INT(10*RND(1)-5):PRINT A(I,J);:NEX T J:PRINT:NEXT I 40 DIM P(N):FOR I=1 TO N:FOR J=1 TO M 50 IF A(I,J)=0 THEN C=C+1:NEXT J ELSE NEXT J 60 P(I)=C:C=0:NEXT I 70 PRINT"Количество нулевых элементов по строкам:":FOR K=1 TO N:? P(K) ;:NEXT 80 FOR K=1 TO N:IF P(K)<>0 THEN S=S+1:NEXT K ELSE NEXT K 90 PRINT:PRINT"Количество строк с нулевыми элементами:";S:END З а д а ч а 20. Дан целочисленный массив L(N,M). Найдите наименьшее ────────────── число K, обладающее таким свойством: хотя бы в одной строке массива все элементы не превосходят K. NEW Ok 20 INPUT "Введите значения N и M";N,M:IF N=1 OR M=1 THEN 20 30 DIM L(N,M):G=RND(-TIME) 40 FOR I=1 TO N:FOR J=1 TO M:L(I,J)=INT(10*RND(1)):PRINT L(I,J);:NEXT J:PRINT:NEXT I 50 FOR I=1 TO N 60 GOSUB 130 70 NEXT I 80 FOR I=1 TO N-1:FOR C=I+1 TO N 90 IF L(I,1)A(I,L) THEN NEXT L:B(I)=A(I,J) ELSE NEXT J:B(I)=A(I,L) 70 NEXT I 80 FOR I=1 TO M-1:FOR J=I+1 TO M 90 IF B(I)<=B(J) THEN NEXT J:PRINT"Число,удовлетворяющее условию:"B(I) ELSE NEXT I:PRINT"Число,удовлетворяющее условию:"B(J) По сути дела условия задач 20 и 21 одинаковы, если, разумеется, масси- вы A и L совпадают! З а д а ч а 22. Постройте алгоритм разложения натуральных чисел на ────────────── простые множители. В какой форме будут представлены ре- зультаты работы этого алгоритма. NEW Ok 560 INPUT"Натуральное число";S:N=S:W$="" 570 I=2 580 IF N/I=FIX(N/I) THEN N=N/I:W$=W$+STR$(I) ELSE I=I+1:GOTO 580 590 IF I=P THEN 110 130 RETURN run 1 1=1 2 2=2 ··· 85 972=2*2*3*3*3*3*3 86 1000=2*2*2*5*5*5 Ok З а д а ч а 25. Придумайте способ нахождения самой легкой и самой тяже- ────────────── лой из 100 монет различной массы, если можно сделать не более 150 взвешиваний на чашечных весах без гирь. (На каждую чашку ве- сов помещается по одной монете; весы показывают, какая из них тяжелее.) NEW Ok 5 'Автор программы: Поляков Сергей (9 класс), 02.01.90 10 WIDTH80:CLS:INPUT"Введите число монет(продолжение сообщений по нажа тию клавиши 'Пробел')";N:IF N/2=FIX(N/2) THEN DIM A(N):X=RND(-TIME) EL SE CLS:RUN 10 20 PRINT "В Вашем кошельке хранятся следующие монеты:" 30 PRINT"────────────────────────────────────────────────" 40 FOR I=1 TO N:A(I)=INT(100*RND(1)+1):PRINT A(I);:NEXT:R1=A(1) 50 PRINT:PRINT"────────────────────────────────────────────────":H$=IN PUT$(1) 60 FOR I=1 TO N-1 STEP 2 70 IF A(I)D1 THEN D1=D 150 PRINT" Большая из 2 только что взятых монет-"D"граммов; после сравнения этих монет ОСТАЕТСЯ монета весом "D1" граммов":PRINT 155 PRINT " ("G"- E ВЗВЕШИВАНИЕ)":PRINT 160 H$=INPUT$(1):GOSUB 200 170 C=C+3:NEXT I 180 PRINT:PRINT"После долгих стараний: ("C" взвешиваний) мы наш ли,что наибольший вес:":PRINT D1"граммов":PRINT 190 PRINT" Mинимальный вес:"R1"граммов":END 200 LOCATE 0,4:FOR F=1 TO 17:FOR J=1 TO 80:PRINT" ";:NEXT:NEXT:LOCATE 0,4:RETURN З а д а ч а 26. Имеется 1000 монет, из которых одна фальшивая (она лег- ────────────── че других). Докажите, что нельзя придумать способ, га- рантирующий нахождение фальшивой монеты за 6 взвешиваний на чашечных ве- сах без гирь. Придумайте способ, гарантирующий нахождение фальшивой моне- ты за 7 взвешиваний. NEW Ok 20 B=1000:D=1:Q=1:PRINT "Мы имеем";B;"монет":GOTO 110 30 I=I+1:PRINT I;"ВЗВЕШИВАНИЕ." 40 A=INT(B/3):PRINT "Разделим все оставшиеся монеты на 4 кучки по";A;" ,";A;",";A;"и";B-3*A-Q+D;"монет." 50 PRINT "Взвесим 2 кучки по";A;"монет." 60 PRINT "Если одна из них легче, то берем эту кучку монет и еще";B-3* A-Q+D;"монеты." 70 PRINT "Остальные монеты не являются фальшивыми." 80 PRINT "Для получения дальнейшей информации нажмите любую клавишу." 90 IF NOT B/3=A THEN Q=Q-1 100 B=A:P$=INPUT$(1):RETURN 110 FOR T=1 TO 6:GOSUB 30:NEXT 120 B=3:D=0:Q=0:GOSUB 30 130 PRINT "Итак, Вы нашли фальшивую монету." З а д а ч а 27. Среди 2·N+1 различных по массе монет нужно найти сред- ────────────── нюю (т.е. такую, которая тяжелее N монет и легче N дру- гих монет). Придумайте способ, позволяющий сделать это не более чем за 100·N взвешиваний на чашечных весах без гирь. 5 'Автор программы: Шарковский Игорь (9 класс), 02.01.90 10 KEY OFF:CLS:COLOR 15,4 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: 60 FOR I=1 TO N 70 A(I)=INT(20*(RND(1))+10):PRINT "│"A(I)"│"; 80 NEXT :PRINT:FOR I=1 TO N:PRINT "└────┘";:NEXT:FOR I=1 TO 1000:NEXT: PRINT: 90 PRINT "Приступим к упорядочению монет по возрастанию ":FOR I=1 TO 1 000:NEXT 100 PRINT :IF N=1 THEN PRINT "Всего-то?":END 110 FOR I=1 TO N-1:FOR J=I+1 TO N 120 IF A(I)>=A(J) THEN SWAP A(I),A(J):K=K+1:NEXTJ:NEXT I ELSE K=K+1:N EXT J:NEXT I 130 PRINT "После упорядочения монеты в Вашем кошельке расположились та к:" 140 FOR I=1 TO N:PRINT"┌────┐";:NEXT:FOR I=1 TO 1000:NEXT:PRINT 150 FOR I=1 TO N :PRINT "│"A(I)"│";:NEXT 160 PRINT:FOR I=1 TO N:PRINT"└────┘";:NEXT:FOR I=1 TO 1000:NEXT:FOR I= 1 TO 4:PRINT:NEXT 170 PRINT "Теперь (наконец-то) приступим к нахождению средней из них ( по массе)":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 " │ " 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. NEW Ok 490 INPUT"Введите N";N:DIM A(N) 500 A(1)=1:PRINT A(1);:FOR I=2 TO N 510 IF I/2=INT(I/2) THEN A(I)=A(I/2)ELSEA(I)=A(INT(I/2))+A(INT(I/2)+1) 520 PRINT A(I);:NEXT:PRINT:PRINT "An=";A(N) 530 END Каждая истинная работа имеет свою красоту. Н.Рерих З а д а ч а 29. Дан целочисленный массив A(N).Найдите наименьшее число ────────────── К элементов, которые нужно "выкинуть" из последователь- ности A(1),A(2),...,A(N), чтобы осталась возрастающая последовательность. 10 DEFINT Q,K,I,J,N,D:INPUT "Укажите количество элементов";N:DIM A(N), Q(N),B(N):X=RND(-TIME) 15 PRINT"Исходная последовательность:" 20 FOR I=1 TO N:A(I)=INT(9*RND(1)):PRINT A(I);:NEXTI 30 FOR I=1 TO N:Q(I)=N-1:NEXT I 40 FOR I=1 TO N-1:FOR J=I+1 TO N 50 IF A(I)Q(I) THEN K=Q(I) 90 NEXT I:D=K 100 PRINT:PRINT"Нужно выбросить:";K;"элементa" 120 FOR I=N TO 1 STEP(-1) 130 IF Q(I)=K THEN B(K)=A(I):K=K+1:NEXT I ELSE NEXTI 135 PRINT"Одна из самых длинных возрастающих подпоследовательностей:"; 140 FOR J=N-1 TO D STEP (-1):PRINT B(J);:NEXTJ run Укажите количество элементов? 10 Исходная последовательность: ·7··4··2··4··7··8··2··6··8··3 Нужно выбросить: 6 элемента Одна из самых длинных возрастающих подпоследовательностей: ·2··4··6··8 Ok В этой задаче программными строками 10-20 описываем массив A и заполня- ем его псевдослучайными числами; это делается для формирования тестовых примеров без утомительного набора их на клавиатуре. Строки с 30 по 100 по- зволяют с помощью дополнительного массива Q найти наименьшее число K эле- ментов, которые нужно "выкинуть" из массива, чтобы осталась возрастающая подпоследовательность. И наконец, в строках 120-140 происходит выделение этой максимальной по длине подпоследовательности. З а д а ч а 30. Дано три целочисленных массива A(N), B(N), C(N). Из- ────────────── вестно, что существуют целые числа, встречающиеся во всех трех таблицах. Найдите одно из таких чисел. NEW Ok 20 INPUT"Введите размер массивов";N 30 Z=RND(-TIME) 40 PRINT "Первый массив" 50 DIM S(N) 60 FOR I=1 TO N:X=INT(N*RND(1)):S(I)=X:PRINT S(I);:NEXT:PRINT 90 PRINT"Второй массив" 100 DIM K(N) 110 FOR I=1 TO N:X=INT(N*RND(1)):K(I)=X:PRINTK(I);:NEXT:PRINT 130 PRINT"Третий массив" 140 DIM P(N):FOR I=1 TO N:X=INT(N*RND(1)):P(I)=X:PRINTP(I); 160 NEXT:PRINT 170 DIM U(N,3):Y$="а его нет!" 180 FOR I=1 TO N:M=1:U(I,M)=S(I):NEXT 210 FOR I=1 TO N:M=2:U(I,M)=K(I):NEXT 240 FOR I=1 TO N:M=3:U(I,M)=P(I):NEXT 270 FOR I=1 TO 3:FOR J=1 TO N:FOR R=1 TO 3:FOR K=1 TO N 310 IF U(J,I)=U(K,R) THEN NEXT R:Y$=STR$(U(J,I)) ELSE NEXT K,J,I 320 PRINT 330 PRINT"Общий элемент: ";Y$:END З а д а ч а 30∗. Найдем теперь все числа, обладающие свойством, описан- ─────────────── ным в задаче 30. NEW Ok 10 INPUT"Сколько чисел в каждой таблице";N:DIM A1(N),A2(N),A3(N) 20 INPUT"Чему равен максимальный элемент";F 30 FOR I=1 TO N:A1(I)=INT(2*F*RND(1)-F):PRINT A1(I);:NEXT:PRINT:PRINT 40 FOR I=1 TO N:A2(I)=INT(2*F*RND(1)-F):PRINT A2(I);:NEXT:PRINT:PRINT 50 FOR I=1 TO N:A3(I)=INT(2*F*RND(1)-F):PRINT A3(I);:NEXT:PRINT:PRINT 60 PRINT "А вот те числа, которые встречаются в трех таблицах сразу:" 70 FOR I=1 TO N:FOR J=1 TO N:FOR K=1 TO N 80 IF A1(I)=A2(J) AND A1(I)=A3(K) THEN PRINT A1(I);:NEXT I ELSE NEXT K ,J,I 90 PRINT :PRINT"Увы, но все числа, встречающиеся в трех таблицах сразу , уже выведены на экран." З а д а ч а 31. Даны два слова X$ и Y$. Проверить,можно ли из символов, ────────────── входящих в слово X$, составить слово Y$. Символы можно переставлять, но каждый символ можно использовать не более одного раза! NEW Ok 10 INPUT X$,Y$ 15 IF X$="" OR Y$="" THEN PRINT "Нет":GOTO 10 20 FOR I=1 TO LEN(Y$):FOR J=1 TO LEN(X$) 30 IF MID$(Y$,I,1)=MID$(X$,J,1) THEN X$=LEFT$(X$,J-1)+RIGHT$(X$,LEN(X$ )-J):A$="Да":NEXT I ELSE A$="Нет":NEXT J 50 PRINT A$:END run А затем... Ok Подумайте,почему ? молоко,комоло print LEN(x$) x$="" ? Да 0 Ok Ok З а д а ч а 32. Составьте алгоритм, находящий по целым величинам A, B ────────────── и С такие целые числа X и Y, что A·X+B·Y=C (если та- кие X и Y есть). NEW Ok 30 PRINT "Ax+By=C (Диофантовы уравнения)" 40 INPUT"Чему равны A,B,C";A,B,C 50 A1=A:B1=B:C1=C 60 'Нам нужно найти число M такое, которое в 5 раз больше числа цифр в максимальном по модулю из чисел A, B, C (строки 60-80) 70 CJ=ABS(A):IF ABS(B)>CJ THEN CJ=ABS(B) 80 IF ABS(C)>CJ THEN CJ=ABS(C) 90 CJ$=MID$(STR$(CJ),2):M=5*LEN(CJ$) 100 DIM Q(M) 110 N=0:I=0:D=ABS(A):S=ABS(A):R=ABS(B) 120 I=I+1:IF NOT R<>0 THEN 160 130 FOR W=1 TO 0 STEP 1 '∗∗∗∗ WHILE ∗∗∗∗ 140 N=I:Q[I]=FIX(S/R):D=R:R=S-R*Q[I]:S=D 150 I=I+1:W=R<>0:NEXT W '∗∗∗∗ WEND ∗∗∗∗ 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 сделаем взаимно простыми 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'Частные решен ия 210 PRINT "Получено частное решение":PRINT "уравнения: (";STR$(A1);")* x+(";STR$(B1);")*y=";C1 220 PRINT "X0=";STR$(X);SPC(2);"Y0=";STR$(Y) 230 PRINT "Общее решение:":PRINT "Xi=";STR$(X);"+i*(";STR$(B1);") и Yi =";STR$(Y);"-i*(";STR$(A1);")," 240 PRINT "где i- целое число." 250 ' Таблица тестовых примеров 260 '┌────┬────┬─────┬──────┬────────┐ 270 '│ A │ B │ C │ X │ Y │ 280 '│────│────│─────│──────│────────│ 290 '│1000│ 23 │ 1046│ -22 │ 1002 │ 300 '│ 0 │ 0 │ 0 │Неопределенность 310 '│ 57 │-103│47009│ 73 │ -416 │ 320 '│ 10 │ 12 │ 578 │ -1 │ 49 │ 330 '│ 10 │ 12 │ 97 │ Нет решения │ 340 '└───────────────────────────────┘ А вы, друзья, как ни садитесь, Все в музыканты не годитесь. И.Крылов З а д а ч а 33. Перестановкой N чисел называется последовательность ────────────── A(1),A(2),...,A(N), в которой встречаются по одному разу все числа от 1 до N. (Например, перестановками трех чисел являются: (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1) и других перестановок трех чисел нет.) Постройте алгоритм, печатающий все перестановки N чисел. Этой проблеме посвящено много публикаций. Она имеет давнюю историю, ее возникновение можно отнести к началу XVII века, когда в Англии зародилось особое искусство колокольного боя, основанного, если говорить упрощенно, на выбивании на N различных колоколах всех n! перестановок. Перестановки эти следовало выбивать "по памяти", что способствовало разработке сторон- никами этого искусства первых простых методов систематического перечисле- ния всех перестановок (без повторений). Некоторые из этих незаслуженно за- бытых методов были переоткрыты в настоящее время в связи с появлением циф- ровых машин. Это искусство просуществовало до наших дней, поскольку знаме- нитая Книга рекордов Гиннеса содержит упоминание о выбивании всех 8!=40320 перестановок на 8 колоколах в 1963 году;установление этого рекор- да потребовало 17 часов 58.5 минут! Конечно, использование цифровых машин позволяет генерировать перестановки значительно быстрее,однако разница не так уж велика, как можно было бы подумать - за 18 часов даже самый быст- рый компьютер не сможет получить все перестановки n-элементного множества, если n>13 (с другой стороны, перестановки 8-элементного множества можно получить в течение доли секунды). Это простое следствие того факта,что n! растет весьма быстро с ростом n. Укажем алгоритм получения всех перестановок из N элементов. Пусть имеется множество элементов A={A ,A ,...,A }. Обозначим две разные 1 2 N перестановки этих элементов i i i j j j А =[A ,A ,...,A ] и A =[A ,A ,...,A ] . i 1 2 N j 1 2 N Определение. Две перестановки называются у п о р я д о ч е н н ы м и ─────────── в л е к с и к о г р а ф и ч е с к о м смысле, A >A , если: i j i j 1) A >A или 1 1 2) существует целое k из [2,N] такое, что 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. Лексикографически упорядочены фамилии владельцев телефо- ───────────── нов в телефонном справочнике. Таким образом, если мы научимся генерировать перестановки в лексикогра- фическом порядке, то сможем получать все возможные варианты - начиная с "самой маленькой" и кончая "самой большой". Пусть исходное множество, для которого нужно получить все перестанов- ки, есть множество натуральных чисел 1,2,...,N. Положим, что исходная пе- рестановка - 1,2,...N. Текущую перестановку обозначим A=[A ,A ,...,A ] . 1 2 N Предлагается следующая последовательность действий (можно доказать,что она всегда приводит к получению лексикографически упорядоченных перестано- вок). 1. Просматриваем A справа налево в поисках самого правого i, для кото- рого A A(J+1)ANDJ>0 THEN J=J-1:GOTO 50 60 I=J 70 IF I>0 THEN J=N:GOTO 80 ELSE GOTO 110 80 IF A(I)>A(J) THEN J=J-1:GOTO 80 90 SWAP A(I),A(J):P1=I+1:P2=N 100 IF P10 THEN GOTO 40 run ? 3 1 2 3 2 3 1 1 3 2 3 1 2 2 1 3 3 2 1 Ok Очевидно, программа остается работоспособной и тогда, когда элементами исходного множества являются любые числа (не только натуральные),между ко- торыми установлено соотношение порядка. Кстати, какие изменения нужно внести в программу,чтобы она строила все перестановки множества букв латинского алфавита? Может ли она проделать те же преобразования с буквами русского алфавита? З а д а ч а. Написать все предложения,которые можно составить из слов ─────────── "Ваши прекрасные глаза", "прекрасная маркиза","от любви", "сулят", "мне", "смерть" путем их всевозможных перестановок (данная ситу- ация обыгрывается в пьесе Мольера "Мещанин во дворянстве"). З а д а ч а 33.1 Перестановки с повторениями. ──────────────── NEW Ok 5 DEFINT N,K,J,I:INPUT"Число элементов";N:DIM A(N) 10 W=0:FOR L=1 TO N:INPUT A(L):NEXT L 12 FOR L1=1 TO N-1:FOR L2=L1 TO N 14 IF A(L1)>A(L2) THEN SWAP A(L1),A(L2) 16 NEXT:NEXT 20 I=N 30 GOTO 110 40 PRINT W;SPC(5);:FOR K=1 TO N:PRINT A(K);:NEXT K:PRINT:J=N-1 50 IF A(J)>=A(J+1)AND J>0 THEN J=J-1:GOTO 50 60 I=J 70 IFI>0 THEN J=N:GOTO80 ELSE GOTO 110 80 IF A(I)>=A(J) THEN J=J-1:GOTO 80 90 SWAP A(I),A(J):P1=I+1:P2=N 100 IFP10 THEN W=W+1:GOTO 40 run Число элементов? 4 ? 1 ? 2 ? 2 ? 2 ·1·······1··2··2··2 ·2·······2··1··2··2 ·3·······2··2··1··2 ·4·······2··2··2··1 Ok З а д а ч а 34. Дан целочисленный массив T(N). Найдите наименьшее нату- ────────────── ральное число X, не обладающее следующим свойством: "можно так вычеркнуть некоторые числа таблицы T, чтобы сумма оставшихся равнялась X. NEW Ok 10 INPUT"Введите количество элементов в массиве(больше чем 1):";N:DIM T(N) 20 PRINT:PRINT" Натуральные элементы массива перeд Вами:":PRINT"────── ─────────────────" 30 FOR I=1 TO N:T(I)=INT(3*RND(-TIME))+1:PRINT T(I);:NEXT:PRINT 40 FOR I=1 TO N-1:FOR J=I+1 TO N 50 IF T(I)>=T(J) THEN SWAP T(I),T(J) 60 NEXT J,I:PRINT"───────────────────────" 70 PRINT"Искомое число:"; 80 IF T(1)=1 THEN GOSUB 100:PRINT X:END ELSE X=1:PRINT X:END 90 '∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ 100 S=T(1):A$="Продолжить":K=2 110 IF NOT(K<=N AND A$="Продолжить") THEN X=S+1:PRINT X:END 120 FOR I=1 TO 0 STEP 1 130 IF T(K)<=S+1 THEN S=S+T(K):K=K+1 ELSE A$="Закончить" 140 I=(K<=N AND A$="Продолжить"):NEXT 150 X=S+1:RETURN З а д а ч а 35. Составьте алгоритм подсчета числа способов, которыми ────────────── можно уплатить K рублей купюрами в 1,3,5,10,25,50,100 NEW рублей. Ok 10 INPUT N 20 PRINT"Могу уплатить так:" 30 PRINT"100 50 25 10 5 3 1" 40 PRINT"─────────────────────" 50 FOR A=0 TO N\100:FOR B=0 TO N\50:FOR C=0 TO N\25:FOR D=0 TO N\10:FO R F=0 TO N\5:FOR I=0 TO N\3:FOR J=0 TO N 60 IF 100*A+50*B+25*C+10*D+5*F+3*I+J=N THEN L=L+1:PRINT A;B;C;D;F;I;J 70 NEXT J,I,F,D,C,B,A 80 PRINT"─────────────────────" 90 PRINT"Число способов:";L З а д а ч а 36. В стране имеется N городов, соединенных авиационным ────────────── сообщением. Стоимость билета из I-го города в J-й запи- сана в массиве A[N,N]. Составьте алгоритм, находящий стоимость перелета из I-го города в J-й по самому дешевому маршруту (возможно с пересадками). NEW Ok 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] 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 80 PRINT"Таблица минимальных цен:" 90 FOR I=1 TO N 100 FOR J=1 TO N:G[J]=J:NEXT J 110 G[1]=I:G[I]=1:S=1 120 FOR J=1 TO N:ST[I,J]=CC[I,J]:NEXT J 130 IF S>=N THEN 210 ELSE FOR R=1 TO 0 140 MIN=ST[I,G[S+1]]:JM=S+1 150 IF S+2>N THEN 170 ELSE FOR J=S+2 TO N 160 IF ST[I,G[J]]N THEN 200 ELSE FOR J=S+1 TO N 190 IF ST[I,G[S]]+CC[G[S],G[J]]""THEN 240 230 PRESET(EL,165):PRINT #1,P$+"," 240 M$=M$+P$:PRESET(EL,165):PRINT #1,P$:EL=EL+16 250 IF LEN(M$)<2 THEN 210 260 M=VAL(LEFT$(M$,1)):N=VAL(RIGHT$(M$,1)):IF M<1 OR M>K OR N<1 OR N>E THEN CLS:P$="":M$="":GOTO 20 270 P$="":M$="":EL=0 280 DATA 1,1,1,2,7,10,16,23,13,1,1,2,7,15,0,0,0,192,240,112,56,24,24,2 4,56,48,16,8,252,254,0,0 290 FOR TI=1 TO 32:READ R:XO$=XO$+CHR$(R):NEXT 300 SPRITE$(1)=XO$ 310 DIM A(K,E) 'О с н о в н а я п р о г р а м м а 320 G=8:I=M:J=N:A(I,J)=1:XX=(J-1)*16+X8:YY=(I-1)*16+Y8:PUT SPRITE 1,(X X,YY),10,1 330 FOR V=-2 TO 2:FOR H=-2 TO 2'Перебор всевозможных вариантов хода ко ня 340 IF V=0 OR H=0 OR ABS(V)=ABS(H) THEN 350 ELSE GOSUB 500 'Переход на подпрограмму, определяющую оптимальный вариант хода коня. 350 NEXT H:NEXT V 360 COLOR15,1,8:PSET(190,45):PRINT #1,SED:COLOR1,15,8 370 COLOR15,1,8:PSET(190,60):PRINT #1,I;",";J:COLOR 1,15,8 380 SED=SED+1 'Число ходов 390 I=I+V2:J=J+H2:XX=(J-1)*16+X8:YY=(I-1)*16+Y8:A(I,J)=1 400 PUT SPRITE 1,(XX,YY),10,1 'Перемещение спрайта 410 IF (I-V2+J-H2)MOD2<>0 THEN GOTO 430 420 COLOR15,1,8:PRESET((J-H2-1)*16+X8+5,(I-V2-1)*16+Y8+5):PRINT #1,"∗" :COLOR1,15,8:GOTO 440 430 PRESET((J-H2-1)*16+X8+5,(I-V2-1)*16+Y8+5):PRINT #1,"∗"'Заполнение пройденных полей 440 PRESET(190,45):PRINT #1,SED 450 PRESET(215,45):PRINT #1,"ход" 460 PRESET(190,60):PRINT #1,I;",";J 470 FOR II=1 TO K:FOR JJ=1 TO E 480 IF A(II,JJ)=1 THEN NEXT JJ:NEXT II:GOTO 610 ELSE IF G>0 THEN G=8:G OTO 330 490 'Подпрограмма, считающая число возможных ходов с тех полей,на кото рые конь мог бы пойти, и выделение из них минимального. 500 IF I+V=>1 AND I+V=1 AND J+H==1 AND I+V1<=K AND J+H1>=1 AND J+H1<=E THEN 550 ELSE 560 550 IF A(I+V1,J+H1)=0 THEN L=L+1:GOTO 560 ELSE 560 560 NEXT H1,V1 570 IF(M=4 AND N=1)OR(M=4 AND N=4)OR(M=7AND N=2) THEN 590 ELSE 580 580 IF L=Y6 THEN A$="":GOTO 570 ELSE YY=YY+DO:I=I+1:PUT SPRITE5,( XX,YY),10,20:GOTO 570 710 IF XX+DO>=X6 THEN A$="":GOTO 570 ELSE XX=XX+DO:J=J+1:PUT SPRITE5,( XX,YY),10,20:GOTO 570 730 IF XX-DO=1 THEN 790 ELSE A(I,J)=1:GOSUB1150:Q=5:GOSUB1010:IF(I+J)MOD2 =0 THEN COLOR15,1,8:PRESET(XX+5,YY+5):PRINT #1,"∗":COLOR 1,15,8 ELSE P RESET(XX+5,YY+5):PRINT #1,"∗" 770 F=1:K1=I:K2=J:GOTO 570 790 FOR V4=-2 TO 2:FOR H4=-2 TO 2 810 IF V4=0 OR H4=0 OR ABS(V4)=ABS(H4) THEN NEXT H4,V4 ELSE IF I=K1+V4 AND J=K2+H4 AND A(I,J)<>1 THEN 850 ELSE NEXT H4,V4:GOTO 570 830 GOTO 570 850 K1=I:K2=J:A(I,J)=1:GOSUB1150:Q=Q+5:GOSUB1010:IF (I+J)MOD2=0 THEN C OLOR15,1,8:PRESET(XX+5,YY+5):PRINT #1,"∗":COLOR 1,15,8 ELSE PRESET(XX+ 5,YY+5):PRINT #1,"∗" 870 FOR V5=-2 TO 2:FOR H5=-2 TO 2 890 IF V5=0 OR H5=0 OR ABS(V5)=ABS(H5) THEN 950 910 IF I+V5>K OR I+V5<1 OR J+H5>E OR J+H5<1 THEN 950 ELSE 930 930 IF A(I+V5,J+H5)=1 THEN 950 ELSE BOB=BOB+1 950 NEXT H5,V5 970 IF BOB<>0 THEN BOB=0:GOTO 570 990 GOTO 1050 1010 COLOR 15,8,8:PRESET(45,182):PRINT#1,Q 1030 PRESET(46,182):PRINT#1,Q:COLOR1,15,8:RETURN 1050 FOR L1=1 TO 8:PUT SPRITE 1,(119,79),8,L1:PUTSPRITE2,(135,79),8,L1 +8:FORC=0 TO 35:NEXTC:NEXT 1070 XIT$=INKEY$:IFXIT$="" THEN 1050 ELSE PUT SPRITE1,(0,0),15,L1:PUT SPRITE 2,(16,0),15,L1+8 1090 FOR I1=1 TO 8:FORJ1=1 TO 8 1110 IF(I1+J1)MOD2=0 THEN NEXTJ1,I1 ELSECOLOR15,1,8:PSET((I1-1)*16+X8+ 5,(J1-1)*16+Y8+5):PRINT #1,"∗":COLOR1,15,8:NEXTJ1,I1 1130 GOSUB 1150:GOTO 1190 1150 COLOR 8,15,8:PSET(45,182):PRINT #1,Q 1170 PSET(46,182):PRINT #1,Q:COLOR 1,15,8:RETURN 1190 IF Q<=M1 THEN 1270 1210 COLOR 8,5,8:PSET(225,182):PRINT #1,M1:PSET(226,182):PRINT #1,M1:C OLOR1,15,8 1230 M1=Q 1250 COLOR 5,8,8:PRESET(225,182):PRINT #1,M1:PRESET(226,182):PRINT #1, M1:COLOR1,15,8 1270 ERASE A:F=0:Q=0:CLOSE:GOTO 50 1280 DATA 0,0,127,128,128,190,179,179,190,179,179,179,190,128,128,127, 0,0,255,0,0,51,51,51,51,30,12,12,12,0,0,255 1290 DATA 0,0,0,0,0,127,128,191,190,179,190,128,127,0,0,0,0,0,0,0,0,25 5,0,51,51,30,12,0,255,0,0,0 1300 DATA 0,0,0,0,0,0,0,0,0,255,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,255,0,0, 0,0,0,0 1310 DATA 0,0,0,0,0,127,128,190,179,190,191,128,127,0,0,0,0,0,0,0,0,25 5,0,12,30,51,51,0,255,0,0,0 1320 DATA 0,0,127,128,128,190,179,179,179,190,179,179,190,128,128,127, 0,0,255,0,0,12,12,12,30,51,51,51,51,0,0,255 1330 DATA 0,0,255,0,0,63,51,53,60,52,49,51,63,0,0,255,0,0,254,1,1,25,2 5,25,25,25,1,25,25,1,1,254 1340 DATA 0,0,0,0,0,255,0,63,60,53,63,0,255,0,0,0,0,0,0,0,0,254,1,25,2 5,1,25,1,254,0,0,0 1350 DATA 0,0,0,0,0,255,0,63,53,60,63,0,255,0,0,0,0,0,0,0,0,254,1,25,1 ,25,25,1,254,0,0,0 1360 DATA 0,0,255,0,0,63,51,49,52,60,53,51,63,0,0,255,0,0,254,1,1,25,2 5,1,25,25,25,25,25,1,1,254 Если в задаче меньше трех переменных, это не задача; если больше восьми - она неразрешима. Закон Мэрфи З а д а ч а 38. Существуют способы расстановки 8 ферзей на шахматной ────────────── доске такие, что они не бьют друг друга. Составьте ал- горитм, отыскивающий хотя бы один из них. NEW Ok 10 'Расстановка 8 ферзей. Минимальное время работы - 14 минут. 30 COLOR 1,15,8:SCREEN 2,1:VV=0:OPEN"grp:" AS#1 40 DATA a,b,c,d,e,f,g,h 50 A$=CHR$(0)+CHR$(16)+CHR$(146)+CHR$(84)+CHR$(40)+CHR$(124)+CHR$(0)+C HR$(0) '"Внешний облик" ферзей. 60 FOR J1=20 TO 160 STEP 20:FOR J2=20 TO 160 STEP 20 70 LINE(J2,J1)-(J2+20,J1+20),2,B 80 NEXT J2:PRESET(6,J1+6):PRINT #1,J1/20:NEXT J1 90 FOR I=1 TO 8:READ C$:PRESET (20*I+6,182):PRINT #1,C$:NEXT I'Нарисов ано поле. 100 SPRITE$(1)=A$:N1=1:N2=1:N3=1:N4=1:N5=1:N6=1:N7=1:N8=1:GOSUB 500 110 PRESET(184,100):PRINT #1,"Восемь":PRESET(184,110):PRINT #1,"ферзей !":GOSUB 470:SPRITE$(1)=A$ 120 'Проверка условий (строки 120-400). 130 FOR N1=1 TO 8:FOR N2=1 TO 9:IF N2=N1 OR N1-N2=1 OR N2-N1=1 THEN 42 0 140 IF N2=9 THEN N2=1:GOTO 430 150 FOR N3=1 TO 9:IF N3=N1 OR N3=N2 OR N1-N3=2 OR N2-N3=1 OR N3-N1=2 O R N3-N2=1 THEN 410 160 IF N3=9 THEN N3=1:GOTO 420 170 FOR N4=1 TO 9:IF N4=N1 OR N4=N2 OR N4=N3 THEN 400 180 IF N1-N4=3 OR N2-N4=2 OR N3-N4=1 OR N4-N1=3 OR N4-N2=2 OR N4-N3=1 THEN 400 190 IF N4=9 THEN N4=1:GOTO 410 200 FOR N5=1 TO 9:IF N5=N1 OR N5=N2 OR N5=N3 OR N5=N4 THEN 390 210 IF N1-N5=4 OR N2-N5=3 OR N3-N5=2 OR N4-N5=1 OR N5-N1=4 OR N5-N2=3 OR N5-N3=2 OR N5-N4=1 THEN 390 220 IF N5=9 THEN N5=1:GOTO 400 230 FOR N6=1 TO 9:IF N6=N1 OR N6=N2 OR N6=N3 OR N6=N4 OR N6=N5 THEN 38 0 240 IF N1-N6=5 OR N2-N6=4 OR N3-N6=3 OR N4-N6=2 OR N5-N6=1 THEN 380 250 IF N6-N1=5 OR N6-N2=4 OR N6-N3=3 OR N6-N4=2 OR N6-N5=1 THEN 380 260 IF N6=9 THEN N6=1:GOTO 390 270 FOR N7=1 TO 9:IF N7=N1 OR N7=N2 OR N7=N3 OR N7=N4 OR N7=N5 OR N7=N 6 THEN 370 280 IF N1-N7=6 OR N2-N7=5 OR N3-N7=4 OR N4-N7=3 OR N5-N7=2 OR N6-N7=1 THEN 370 290 IF N7-N1=6 OR N7-N2=5 OR N7-N3=4 OR N7-N4=3 OR N7-N5=2 OR N7-N6=1 THEN 370 300 IF N7=9 THEN N7=1:GOTO 380 310 FOR N8=1 TO 9:IF N8=N1 OR N8=N2 OR N8=N3 OR N8=N4 OR N8=N5 OR N8= N6 OR N8=N7 THEN 360 320 IF N1-N8=7 OR N2-N8=6 OR N3-N8=5 OR N4-N8=4 OR N5-N8=3 OR N6-N8=2 OR N7-N8=1 THEN 360 330 IF N8-N1=7 OR N8-N2=6 OR N8-N3=5 OR N8-N4=4 OR N8-N5=3 OR N8-N6=2 OR N8-N7=1 THEN 360 340 IF N8=9 THEN N8=1:GOTO 370 350 GOSUB 500:GOSUB 460 360 NEXT N8 370 NEXT N7 380 NEXT N6 390 NEXT N5 400 NEXT N4 410 NEXT N3 420 NEXT N2 430 NEXT N1 440 SCREEN3:PRESET(20,10):PRINT #1,"ВСЕГО":PRESET(5,80):PRINT #1,"ХОРО ШЕГО" 450 GOTO 450 'Конец программы. 460 VV=VV+1:PRESET(182,2):PRINT #1,"Способ":PRESET(182,11):PRINT #1,"н омер ";VV 470 PRESET(190,160):PRINT #1,"Нажмите":PRESET(190,170):PRINT #1,"любую ":PRESET(190,180):PRINT #1,"клавишу" 480 F$=INPUT$(1):LINE(182,0)-(256,192),15,BF:RETURN 490 'Расстановка 8 ферзей. 500 PUT SPRITE 1,(20*N1+2,20*1+2),8,1 510 PUT SPRITE 2,(20*N2+2,20*2+2),8,1 520 PUT SPRITE 3,(20*N3+2,20*3+2),8,1 530 PUT SPRITE 4,(20*N4+2,20*4+2),8,1 540 PUT SPRITE 5,(20*N5+2,20*5+2),8,1 550 PUT SPRITE 6,(20*N6+2,20*6+2),8,1 560 PUT SPRITE 7,(20*N7+2,20*7+2),8,1 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. Составьте алгоритм, отыскивающий наименьшее нату- ральное число, имеющее два разных таких представления. (Представления 9= 2^3+1^3 = 1^3+2^3 считаются одинаковыми.) NEW Ok 5 PRINT "В каком диапазоне натуральных чисел будем решать задачу?" 10 INPUT P:INPUT N:FOR L=P TO N 20 FOR I=FIX(L^(1/3)+.5) TO 0 STEP(-1):FOR J=0 TO I 30 IF I^3+J^3=L THEN K=K+1:NEXT I ELSE NEXT J,I 40 IF K>=2 THEN GOSUB 100:RA=1:K=0:NEXT L ELSE K=0:NEXT L 50 IF RA<1 THEN PRINT "Таких чисел нет!" 60 END 100 FOR I=FIX(L^(1/3)+.5) TO 0 STEP(-1):FOR J=0 TO I 110 IF I^3+J^3=L THEN PRINT STR$(L);"=";MID$(STR$(I),2);"^3+";MID$(STR $(J),2);"^3":NEXT I ELSE NEXT J,I 120 RETURN run В каком диапазоне натуральных чисел будем решать задачу? ? 1720 ? 1740 1729=12^3+1^3 1729=10^3+9^3 Ok З а д а ч а 40. Составьте алгоритм, вычисляющий по заданным веществен- ────────────── ным числам A, B, C, D величины A·C+B·D и A·D-B·C. Этот алгоритм может использовать промежуточные величины, операции сложения, вы- читания и умножения,причем умножение должно выполняться не более трех раз. NEW Ok 50 INPUT"Чему равны A,B,C,D";A,B,C,D 60 P0=(A+B)*(C+D):P1=A*D:P2=B*C:S1=P0-(P1+P2):S2=P1-P2 80 PRINT "AC+BD=";S1,"AD-BC=";S2 90 END З а д а ч а 41. Подсчитайте,сколько символов слова X используется при ────────────── написании слова Y. NEW Ok 10 R=0:P$="":INPUT"Введите первое слово";X$ 20 INPUT"Введите второе слово";Y$ 25 IF LEN(X$)=0 OR LEN(Y$)=0 THEN PRINT"Не балуйтесь!":RUN 30 L=LEN(X$):U=LEN(Y$) 40 FOR I=1 TO L-1:FOR J=I+1TO L 50 IF MID$(X$,I,1)=MID$(X$,J,1) THEN MID$(X$,J,1)=CHR$(0) 60 NEXT J,I 70 FOR I=1 TO L:FOR J=1 TO U 80 IFMID$(X$,I,1)=MID$(Y$,J,1) AND MID$(X$,I,1)<>CHR$(0) THEN P$=P$+MI D$(X$,I,1):R=R+1:N$=MID$(X$,I,1):NEXT I 90 IF N$=MID$(X$,L,1) THEN 120 100 NEXT J 110 NEXT I:X$="":Y$="" 120 PRINT"Из первого слова используется";R;"букв для написания второго" 125 PRINT 130 IF LEN(P$)>=2 THEN PRINT "Эти буквы: ";P$ 140 IF LEN(P$)=1 THEN PRINT "Эта буква: ";P$ 150 RUN 10 З а д а ч а 42. Цифры 1,2,3,4,5,6,7,8,9 соединить знаками действий ────────────── +, -, *, / так, чтобы в результате выполнения действий слева направо (без учета приоритета!) получилось заданное число М. 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: 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)="*" ' расположения символов +,-,*,/ меж- 100 IF I=4 THEN A=A/2:A$(2)="/" ' ду цифрами 1,2,3,4,5,6,7,8,9 ∗∗∗ 110 IF J=1 THEN A=A+3:A$(4)="+" 120 IF J=2 THEN A=A-3:A$(4)="-" 130 IF J=3 THEN A=A*3:A$(4)="*" 140 IF J=4 THEN A=A/3:A$(4)="/" 150 IF K=1 THEN A=A+4:A$(6)="+" 160 IF K=2 THEN A=A-4:A$(6)="-" 170 IF K=3 THEN A=A*4:A$(6)="*" 180 IF K=4 THEN A=A/4:A$(6)="/" 190 IF L=1 THEN A=A+5:A$(8)="+" 200 IF L=2 THEN A=A-5:A$(8)="-" 210 IF L=3 THEN A=A*5:A$(8)="*" 220 IF L=4 THEN A=A/5:A$(8)="/" 230 IF N=1 THEN A=A+6:A$(10)="+" 240 IF N=2 THEN A=A-6:A$(10)="-" 250 IF N=3 THEN A=A*6:A$(10)="*" 260 IF N=4 THEN A=A/6:A$(10)="/" 270 IF S=1 THEN A=A+7:A$(12)="+" 280 IF S=2 THEN A=A-7:A$(12)="-" 290 IF S=3 THEN A=A*7:A$(12)="*" 300 IF S=4 THEN A=A/7:A$(12)="/" 310 IF P=1 THEN A=A+8:A$(14)="+" 320 IF P=2 THEN A=A-8:A$(14)="-" 330 IF P=3 THEN A=A*8:A$(14)="*" 340 IF P=4 THEN A=A/8:A$(14)="/" 350 IF R=1 THEN A=A+9:A$(16)="+" 360 IF R=2 THEN A=A-9:A$(16)="-" 370 IF R=3 THEN A=A*9:A$(16)="*" 380 IF R=4 THEN A=A/9:A$(16)="/" 390 IF A=M THEN G=G+1: GOTO 420 395 LOCATE 16,7: PRINT I;J;K;L;N;S;P;R; 400 NEXT R,P,S,N,L,K,J,I 410 IF W=4 THEN PRINT "УВЫ...": END ELSE END 420 FOR Y=1 TO 17 STEP 2: A$(Y)=STR$((Y+1)/2):NEXT Y 430 LOCATE 0,10+G: FOR Y=1 TO 17 440 PRINT A$(Y);:NEXT Y 450 IF I=4 AND R=4 THEN ?:?"ВСЕ.":END ELSE W=4:GOTO 400 run Число M ? 45 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 1 + 2 + 3 - 4 * 5 - 6 - 7 + 8 * 9 1 + 2 + 3 - 4 * 5 - 6 * 7 + 8 + 9 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 21 I=T K=0 TO 9 30 S=(I-INT(I/10)*10)+(INT(I/10)-IN 30 A%(I+J+K)=A%(I+J+K)+1:NEXT K,J T(I/100)*10)+INT(I/100):L=0:P=9 ,I 40 IF S<10 THEN P=S ELSE IF S>=19 T 40 N=1:FOR I=1 TO27:A%(I)=A%(I)^2 HEN L=S-18 ELSE 50 N=N+A%(I):NEXT I 50 FORJ=LTO P:FOR K=LTOP:FOR N=LTOP 60 PRINT"Счастливых билетов:";N:P 60 IF S=J+K+N THEN C=(((I*10)+J)*10 RINT"Время работы программы:";INT +K)*10+N:IF C<=M AND C>=N THEN PRIN (TIME/60);"с" T C;:W=W+1 run 80 NEXT N,K,J,T:PRINTW Счастливых билетов: 55252 run Время работы программы: 14 с ? 0,1000000 Ok 0 001001 ... 999999 55252 Ok Компьютер считает ≈ 4.5 ч! Отметим, что количество C счастливых 2·n - значных чисел (ясно, что 2n под этим понимается:например, 00351 20115 -счастливое десятизначное число) определяется явной формулой: π 1 ⎧┌ sin(10·x)┐2·n C = ─·││──────────│ dx . 2n π ⎭└ sin(x) ┘ 0 Интересно отметить, что количество счастливых 2n - значных чисел в сис- теме счисления по основанию k: π k 1 ⎧┌ sin(k·x)┐2·n C = ─·││──────────│ dx . 2n π ⎭└ sin(x) ┘ 0 З а д а ч а 44. Написать программу, реализующую римскую арифметику. ────────────── Р и м с к а я система счисления относится к непозици- онным системам. Например, запишем число 88 римскими знаками - LXXXVIII. В этой записи смысл каждого знака (символа) не зависит от того места, на ко- тором он стоит. Здесь, например, цифра X повторяется 3 раза и каждый раз означает одну и ту же величину - д е с я т ь единиц. NEW Ok 20 DIM C$,B,B$,W,A,A$,N$,N,T$,L$,K$,T,L,X$ 30 PRINT "Римская арифметика" 40 PRINT "До начала работы нажмите клавишу"+CHR$(34)+"CAPS"+CHR$(34) 50 PRINT "ВНИМАНИЕ!" 60 PRINT "У древних римлян не было цифры 0!" 70 PRINT "Действия производились только над положительными целыми числ ами." 80 PRINT"При делении за результат принимается целая часть частного." 90 GOTO 240 100 ' ∗∗∗∗∗ From ARABIC to ITALIC ∗∗∗∗∗ 110 DATA 1000,M,900,CM,500,D,400,CD,100,C,90,XC,50,L,40,XL,10,X,9,IX,5 ,V,4,IV,1,I 120 RESTORE 110:C$="" 130 READ B,B$ 140 IF B<=W THEN C$=C$+B$:W=W-B:GOTO 140 150 IF W>0 GOTO 130 160 RETURN 170 ' ∗∗∗∗∗ From ITALIC to ARABIC ∗∗∗∗∗ 180 DATA 1000,M,900,CM,500,D,400,CD,100,C,90,XC,50,L,40,XL,10,X,9,IX,5 ,V,4,IV,1,I 190 RESTORE 180:N=0 200 READ A,A$ 210 IF A$=LEFT$(N$,LEN(A$))THEN N$=RIGHT$(N$,LEN(N$)-LEN(A$)):N=N+A:GO TO 210 220 IF N$>"" GOTO 200 230 RETURN 240 LINEINPUT "Первое число:";T$ 250 LINEINPUT "Второе число:";L$ 260 LINEINPUT "Знак операции (+,-,*,/,^):";K$ 270 Y$=INKEY$ 280 INPUT "А,может,Вы желаете извлечь корень? (Да/Нет)";Y$ 290 IF Y$="Д" OR Y$="д" THEN N$=T$:GOSUB 180:T=N:W=INT(SQR(T)):GOSUB 1 10:? "Корень из ";T$;" равен: ";C$:GOTO 400 300 IF Y$="Н" OR Y$="н" THEN 310 ELSE 270 310 N$=T$:GOSUB 180:T=N:N$=L$:GOSUB 180:L=N 320 IF K$="+" THEN W=T+L:GOTO 370 330 IF K$="-" THEN W=T-L:GOTO 370 340 IF K$="*" THEN W=T*L:GOTO 370 350 IF K$="/" THEN W=INT(T/L):GOTO 370 360 IF K$="^" THEN W=T^L 370 IF W<0 THEN W=-W:X$="=-" ELSE X$="=" 380 GOSUB 110 390 PRINT T$;K$;L$;X$;C$ 400 RUN 90 П р и м е р 45. Написать программу, которая позволяет генерировать (по- ────────────── лучать) всевозможные с о ч е т а н и я подмножества натуральных чисел {1,2,...,N} по K элементов. Итак, основным множеством является подмножество натуральных чисел {1,2,...,n}. Наиболее естественно рассматривать представление сочетания {A , A , 1 2 ...,A } в виде вектора C=(C ,C ,...,C ),у которого компоненты расположены K 1 2 N в порядке возрастания слева направо (т.е. C < C для любого i), и порож- i i+1 дать эти векторы в лексикографическом порядке. Начинается порождение с со- четания (1,2,...,K). Каждое следующее сочетание строится из предыдущего с помощью следующих простых действий: в ходе просмотра текущего сочетания справа налево в нем находится самый первый элемент, который еще не достиг своего максимального значения; этот элемент увеличивается на единицу, а всем элементам справа от него последовательно присваиваются новые наимень- шие возможные значения. NEW Ok 10 INPUT"Укажите N и K";N,K:IF K>N OR K<1 THEN GOTO 10 30 DIM A(N),C(K):FOR I=1TO K:C(I)=I:NEXT 60 P=0:FOR I=1 TO K:IF C(I)=N-K+I THEN P=P+1:NEXT I ELSE NEXT I 80 IF P=K THEN FOR I=1 TO K:PRINT C(I);:NEXT I:END '──▶ 90 FOR J=1 TO K:PRINT C(J);:NEXT J:PRINT 100 FOR J=K TO 1 STEP -1 110 IF C(J)=N-K+J THEN NEXT J:GOTO 60 ELSE C(J)=C(J)+1:IF J+1>K THEN G OTO 60 ELSE FOR I=J+1 TO K:C(I)=C(I-1)+1:NEXT I:GOTO 60 run Укажите N и K? 3,2 1 2 1 3 2 3 Ok Что наша "Жизнь"? Игра! М.Гарднер З а д а ч а 46. Написать программу, реализующую на текстовом экране ────────────── алгоритм игры "Жизнь". Игра "Жизнь" придумана сотрудником Кембриджского университета Дж.Конве- ем. "Жизнь" - многоклеточное сообщество, населяющее пустыню, которая пред- ставляет собой прямоугольную решетку, каждая ячейка которой вмещает одну клетку Жизни. Мерой течения времени служит смена поколений Жизни, принося- щая в колонию клеток смерть и рождение. Чтобы проследить за историей развития колонии,разместим в пустыне клет- ки Жизни в их начальном положении. Смена поколений будет происходить по следующим правилам. 1. Соседями клетки считаются все клетки, находящиеся в восьми ячей- ках, расположенных рядом с данной по горизонтали,вертикали или диагонали. ┌─────────┬────────┬──────────┐ │ M-1,K-1 │ M-1,K │ M-1,K+1 │ │─────────┼────────┼──────────│ │ M,K-1 │ M,K │ M,K+1 │ │─────────┼────────┼──────────│ │ M+1,K-1 │ M+1,K │ M+1,K+1 │ └─────────┴────────┴──────────┘ 2. Если у некоторой клетки меньше двух соседей, она погибает от одино- чества. Если клетка имеет больше трех соседей, она погибает от тесноты. 3. Если рядом с пустой ячейкой окажутся ровно три соседних клетки Жизни, то в этой ячейке рождается новая клетка. 4. Гибель и рождение происходят в момент смены поколений. Таким обра- зом, гибнущая клетка может способствовать рождению новой, но рождающаяся клетка не может воскресить гибнущую, и гибель одной клетки, уменьшив ло- кальную плотность населения, не может предотвратить гибель другой. Колония может все время расти, непрерывно меняя свое расположение,фор- му или число клеток. Однако чаще колония становится в конце концов с т а- ц и о н а р н о й , начиная циклически повторять один и тот же конечный набор состояний. Длина цикла называется п е р и о д о м колонии. (По этому определению период мертвой и пустой колонии равен единице.) Измените приведенную ниже программу так, чтобы она выявляла стационар- ные колонии и сообщала о них. Можете ли Вы придумать хоть какой-нибудь алгоритм, не использующий за- поминания всех предыдущих поколений,который мог бы распознать любую стаци- онарную колонию? История жизни колонии зачаровывает, но она будет еще увлекательнее, ес- ли предстанет в цвете. Каждой клетке при рождении может быть приписан не- который цвет, определяемый, возможно, ее поколением или генами, переданны- ми ей родителями. Циклические, но при этом движущиеся колонии (а таких не- мало!) великолепны в своем сверкающем многоцветном наряде. Любая колония имеет приемника,но не у каждой есть предшественник.Такие изолированные колонии называются с а д а м и Э д е м а . Сад Эдема мож- но увидеть, только если поместить его на плоскость в качестве начальной конфигурации. Подумайте, как использовать программу для нахождения сада Эдема. NEW Ok 3 PRINT"Введите размеры поля: 5 INPUT"3≤ N ≤10";N 6 INPUT"3≤ M ≤14";M 10 K=N-1:L=M-1 20 DIM A(N,M),B(K,L),A1$(N,M),B1$(K,L) 30 W=RND(-TIME):CLS:PRINT"Игра";CHR$(34);"ЖИЗНЬ";CHR$(34):LOCATE 0,4,0 40 FOR I=1 TO K 50 FOR J=1 TO L 60 A(I,J)=INT(2*RND(1)):IF A(I,J)=1 THEN A1$(I,J)=CHR$(155) ELSE A1$(I ,J)="*" 70 PRINT A1$(I,J);SPC(2);:NEXT J:PRINT:PRINT:NEXT I 80 P=0 90 FOR I=1 TO K:FOR J=1 TO L 100 P=A(I-1,J-1)+A(I-1,J)+A(I-1,J+1)+A(I,J-1)+A(I,J+1)+A(I+1,J-1)+A(I+ 1,J)+A(I+1,J+1) 110 IF A(I,J)=0 THEN IF P=3 THEN B(I,J)=1 ELSE B(I,J)=0 ELSE IF P=2 OR P=3 THENB(I,J)=1 ELSE B(I,J)=0 120 NEXT J:NEXT I 130 FOR I=1 TO K:FOR J=1 TO L:IF B(I,J)<>A(I,J)THEN 150 ELSE NEXT:NEXT 140 PRINT "Колония стационарна!" 145 GOTO 145 150 LOCATE0,4 160 FOR I=1 TO K:FOR J=1 TO L 170 A(I,J)=B(I,J) 180 IF B(I,J)=1 THEN B1$(I,J)=CHR$(155)ELSE B1$(I,J)="*" 190 PRINT B1$(I,J);SPC(2);:NEXT:PRINT:PRINT:NEXT 200 LOCATE0,0,0:GOTO80 З а д а ч а 47. Написать программу, реализующую проверку правильности ────────────── расстановки круглых скобок в математических выражениях. NEW Ok 10 LINEINPUT "Введите строку, содержащую открывающие и закрывающие кру глые скобки:";A$ 15 IF LEFT$(A$,1)<>"("THEN GOSUB45:END 20 FOR I=1 TO LEN(A$) 25 IF MID$(A$,I,1)="(" THEN K=K+1 ELSE IF MID$(A$,I,1)=")"THEN K=K-1 30 IF K<0 THEN GOSUB45:END ELSE NEXT 35 IF K<>0 THEN GOSUB45 ELSE PRINT"Скобки расставлены правильно!" 40 END 45 PRINT"Скобки расставлены неправильно!":RETURN Приведем алгоритм, который для любого слова в алфавите {(,)}позволяет выяснить, является ли это слово правильным скобочным выражением.Этот алго- ритм называется способом п о д с ч е т а с к о б о к . Сопоставим слову A в алфавите {(,)}, состоящему из n букв, числовой массив A , A ,..., A , 1 2 n заменяя каждую левую скобку на 1, и каждую правую скобку - на -1.Этот мас- сив назовем и з о б р а ж е н и е м слова A. Имеет место следующая Т е о р е м а. Массив A , A ,..., A , где A =±1 , i=1, 2,..., n ───────────── 1 2 n i является изображением правильного скобочного выражения тогда и только тог- да, когда α) A =1; 1 k β) для каждого k такого что 1R AND K<>R1 THEN Q$=Q$+MID$(P$,K,1) 50 NEXT 60 IF S$=S1$ THEN Q$=Q$+"1" ELSE Q$=Q$+"0" 70 P$=Q$:IF LEN(P$)>1 THEN 15 ELSE PRINT"...а белых зерен в банке изначально было";S XII.2. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ Один человек купил трех коз и заплатил 3 рубля. Спрашивается: по чему каждая коза пошла? Старинная задача-шутка (конец ХVI века) 1. Для запоминания числа π иногда используют "магические" фразы, напри- мер:"это я знаю и помню прекрасно пи многие знаки мне лишни напрасны" или "кто и шутя и скоро пожелаетъ пи узнать число ужъ знаетъ". Число букв в каждом слове любой из данных фраз представляет собою некоторую цифру чис- ла π: "это"-3, "я"-1, "знаю"-4 и т.д. Вывести на печать число π, используя любую из указанных фраз. 2. В одной математической книге наборщик вместо выражения 2^5·9^5 на- брал 2592.Корректор эту серьезную ошибку пропустил,и книга вышла в свет в таком виде. Эту книгу изучало много математиков,все предыдущие и последую- щие вычисления проверялись, а эту явную ошибку, пропущенную наборщиком и корректором, никто не заметил. Как же это могло случиться? Дело в том, что 2^5·9^2=2592 . Это, по-ви- димому, единственный в своем роде числовой курьез! Проверьте. 3. Написать программу игры на ЭВМ под названием "быки и коровы". Прави- ла игры чрезвычайно просты. Один из партнеров - ведущий. Он задумывает лю- бое четырехзначное число. Требуется лишь, чтобы ни одна из составляющих это число цифр не повторялась.Задача другого партнера (назовем его просто игроком) - отгадать это число. Игрок называет пробные числа. Игра заканчи- вается, если названо число, задуманное ведущим. Чем меньше ходов-попыток потребуется для этого игроку, тем лучше он играет. Ведущий помогает игро- ку подсказками. Что это за подсказки,- рассмотрим на примере. Предположим, задумано число 9480. Назовем его к о д о м . Как и пред- писывается условиями игры, все цифры в коде различны. Игрок называет свое пробное число 7984. Ведущий сравнивает его с кодом 9480. Так как числа не совпадают, то игра не закончена. Ведущий сообщает игроку количество "бы- ков" и "коров", содержащихся в предложенном им пробном числе. "Быками" на- зывают те его цифры, которые по значению и позиции совпадают с соответст- вующими цифрами задуманного кода. В нашем примере "бык" один - цифра 8. "Коровы" - это цифры, которые совпадают с цифрами задуманного кода, но на- ходятся в иных позициях. В числе 7984 "коров" две: 9 и 4. Понятно, что от- гадать код или назвать четыре "быка" - это одно и тоже. 4. Написать программу определения соответствующего дня недели по извест- ным целым числам: J - число, М - месяц, А - год,применяя метод М.Ленуара, который заключается в следующем: 1) вычислить величину N: если месяц - январь или февраль високосного года, то N=1; если месяц - январь или февраль обычного года, то N=2; в других случаях N=0. Чтобы узнать, является ли год високосным, можно действовать так: a) разложить год на две части А1 и А2,причем: А1 содержит 2 старшие цифры года, А2 содержит 2 младшие цифры года; b) если А2=0 и А1 делится на 4, то год високосный; c) если А2<>0, то год високосный, если А2 делится на 4; 2) вычислить "код" дня С по формуле: С=[365.25·А2]+[30.56·М]+J+N; 3) вычислить остаток S от деления С на 7: если S=0, то день - среда; если S=1, то день - четверг; если S=2, то день - пятница,...; если S=6, то день - вторник. Незатейливые головоломки о целых числах веками служили источником обновления ма- тематики. Г.Биркгоф 5. Гольдбахом было высказано предположение, что каждое четное число, большее или равное 4 представимо в виде суммы двух простых. Это предположение до сих пор не доказано и не опровергнуто. Написать программу проверки этой гипотезы для данного четного числа. Результатом выполнения программы должен быть вывод самого числа,если не удалось найти пару простых слагаемых, и вывод пары соответствующих простых чисел, если таковая пара найдена. 6. Составить программу поиска среди чисел n, n+1, ..., 2n так называ- емых б л и з н е ц о в, т.е. двух простых чисел,разность которых равна 2. Если близнецы в указанном диапазоне найдены, то вывести 1; если близнецов нет, то вывести 0. 7. Написать игровую программу "Игры на дорожке". Суть ее в том,что два противника двигают фишки, находящиеся на противоположных сторонах дорожки, разбитой на n полей, например на одной из вертикалей шахматной доски, где дорожка содержит 8 полей. Ходы делаются поочередно.За один ход каждый уча- стник может подвинуть свою фишку не более чем на m полей вперед или назад. При этом нельзя перепрыгивать через фишку партнера и покидать пределы до- рожки. Проигрывает тот, у которого не окажется ходов, т.е.чья фишка будет загнана в одно из двух крайних полей дорожки. 8. Написать программу, определяющую показатель, с которым данное прос- тое p входит в произведение n!. Использовать формулу: 2 3 l α=[n/p]+[n/p ]+[n/p ]+...+[n/p ], где: [] - символ выделения целой части, α - искомый показатель, l=[lg(n)/lg(p)]. Например, если n=367, p=3, то α=180. З а м е ч а н и е. Так можно разложить n! на простые множители,беря за p последовательно все простые числа, меньшие n . 9. Найти число делителей данного числа a. Известно, что если α1 αk a=p1 ╳ ···╳pk - каноническое разложение числа a,и σ(a) - число делителей числа a, то σ(a)=(α1+1)·(α2+1)...(αk+1). Например: σ(720)=30. 10. Найти сумму делителей данного числа a. Известно, что если α1 αk a=p1 ╳···╳ pk - каноническое разложение числа a, и S(a) - сумма делителей числа a, то α1+1 αk+1 (p1 -1) (pk -1) S(a) = ──────────╳ ···╳ ────────── . p1-1 pk-1 Например: S(720)=2418. 11. В разложении числа A на простые множители некоторые из них могут повторяться. Обозначая буквами p1, p2,..., pk различные из них и буквами α1, α2,..., αk кратности их вхождения в A, получим так называемое к а - н о н и ч е с к о е разложение числа A на множители: α1 α2 αk a = p1 ╳p2 ╳···╳pk . Написать программу нахождения канонического разложения данного числа A. 12. Задана последовательность из N чисел. Найти самую длинную подпосле- довательность, обладающую следующим свойством: A(i) < A(i+1) > A(i+2) < A(i+3) > A(i+4)..., для некоторого i∈[1,N]. 13. Д р у ж е с т в е н н ы м и числами называется пара чисел, облада- ющих таким свойством:сумма собственных делителей первого из них равна вто- рому числу, а сумма собственных делителей второго числа равна первому чис- лу. Например, сумма делителей числа 220 равна 1+2+4+5+10+11+20+22+44+55+110=284, а сумма делителей числа 284: 1+2+4+71+142=220 , поэтому числа 220 и 284 - дружественная пара. Вторая дружественная пара (1184 и 1210) была найдена в 1867 году шест- надцатилетним итальянцем Б. Паганини. Написать программу для нахождения дружественных чисел, используя спо- соб, указанный еще в 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, найденная еще Пифагором. Однако теорема Сабита дает дружественные числа и при других n, например: n=4 n=7 А=17296 А=9363584 В=18416 В=9437056 В настоящее время известно, что этими тремя случаями исчерпываются все значения n ≤ 20000, при которых указанный способ дает дружественные числа. 14. Рассмотрим некоторое натуральное число n. Если это не палиндром, то изменим порядок его цифр на обратный и сложим исходное число с получив- шимся. Если сумма - не палиндром, то над ней повторяется то же действие и т.д., пока не получится палиндром. До настоящего времени н е и з в е с т- н о , завершается ли этот процесс для любого натурального n. Даны натуральные числа k, l, m (k≤l). Проверить, верно ли, что для лю- бого натурального числа из диапазона от k до l процесс завершается не поз- днее, чем после m таких действий. З а м е ч а н и е. Назовем натуральное число п а л и н д р о м о м , если оно равно своему обращенному. О б р а щ е н н ы м к числу N назы- вается число, которое записано теми же цифрами, что и N, но в обратном по- рядке. 15. В качестве основания позиционной системы может быть взято о т р и - ц а т е л ь н о е целое число. Например,можно рассмотреть систему с осно- ванием -10.Любое целое N единственным образом представляется в виде суммы s s-1 a·(-10) + a ·(-10) + ··· + a·(-10) + a , где 0 ≤ a ≤ 9 , i=0,...,s. s s-1 1 0 i Запишите данное целое N в системе с основанием -10, т.е. найдите соот- ветствующие числа a , a ,..., a . s s-1 0 16. Известно, что если наудачу выписаны два натуральных числа, то веро- ятность того, что они взаимно просты, равна 6/π² (задача П.Л.Чебышева). Используя этот результат, вычислить число π. 17. Вычислить √ 1+2·√ 1+3·√ 1+4·√ 1+··· Выдающийся индийский математик Рамануджан доказал, что результат равен трем. Наконец, отметим, что очень много интересных и сложных задач приведено в книге С.А.Абрамова, Г.Г.Гнездилова, Е.Н.Капустина, М.И.Селюна "Задачи по программированию" (М.:Наука,1988).