А вы, друзья, как не садитесь, Все в музыканты не годитесь. И.А.Крылов З а д а ч а 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