З а д а ч а 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:FO R 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: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 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 450 IF I=4ANDR=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 году шест- надцатилетним итальянцем Б. Паганини. Написать программу для нахождения дружественных чисел, используя спо- соб, указанный еще в 9-м веке арабским математиком Сабитом ибн Корра. Т е о р е м а С а б и т а . Если все три числа 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 Наконец, отметим, что очень много интересных и сложных задач приведено в книге С.А.Абрамова, Г.Г.Гнездилова, Е.Н.Капустина, М.И.Селюна "Задачи по программированию". М.:Наука,1988.