exercise_text.dvi

Size: px

Start display at page:

Download "exercise_text.dvi"

くにもとじゅふく
7 years ago
Views:

1 Windows 1. (Eratosthenes) ERATOS_2500.BAS, prime_sieve_2500.bas 1

2 BAS a, b a b = q r WARIZAN.BAS! WARIZAN.BAS :! a,b : 1000 INPUT PROMPT " a,b ":a,b a,b a, b PRINT LET q=int(a/b) q a/b LET r=mod(a,b) r a b INT(a/b) PRINT a;" ";b;"=";q;" ";r a, b, q, r a, b, q, r PRINT a;"=";b;" ";q;" ";r ; a b = q r a = b q + r 3. BASIC! ERATOS400.BAS! DIM s(400) s DIM p(100) MAT s=zer s(1) s(400) MAT p=zer MAT MATRIX FOR i=2 TO 20 i 2 20

3 3 FOR j=2*i TO 400 STEP i j 2 i 400 i LET s(j)=1 s(j) NEXT j j NEXT i i LET k=1 k 1 FOR i=2 TO 400 i IF s(i)=0 THEN s(i) LET p(k)=i p(k) =i LET k=k+1 k k +1k IF NEXT i i PRINT "400 "; k-1;" " FOR kk=1 TO k-1 kk k 1 PRINT p(kk); NEXT kk kk 3.1. ERATOS400.BAS ERATOS BAS LET t0=time PRINT " "; k-1;" ";TIME-t0;" " ERATOS BAS FOR j=4 TO STEP 2 LET s(j)=1 NEXT j FOR i=3 TO 1000 step 2 FOR j=2*i TO STEP i LET s(j)=1 NEXT j NEXT i

NEXT kk kk 3.1. ERATOS400.BAS ERATOS1000000.BAS LET t0=time PRINT "1000000 "; k-1;" ";TIME-t0;" " 3.2. 3.1 ERATOS1000000.

4 PRIME_SIEVE.BAS 3.4. r r + 4 ERATOS9999.BAS 3.3 PRIME_SIEVE.BAS 3.2 ERATOS BAS (r + 4) log 10 log 10 = (r+4) (r+4) (r + 4) log n π(n) n lim n π(n) n log n =1 1 log x, m n dx n (0 <m<n) m log x 3.4 n m log n , , , n n p(n), log n, dx log x n dx p(n) log x 2

4 10 (r+4) 9999 10 (r+4) 1 10000 (r + 4) log 10 4.1. n π(n) n lim n π(n) n log n =1 1 log x, m n dx n (0 <m<n) m log x 3.

5 n 1, n PRIME.BAS 5.2. PrevNextPRIME.BAS 5.3. r r +4 WARIZAN9999.BAS 3.4 ERATOS9999.BAS

6 a, b MOD(a,b) a b!congruent.bas INPUT PROMPT " a1,a2, b ":a1,a2,b PRINT a1;" ";a2;" ";MOD(a1+a2,b);"mod" b PRINT a1;" ";a2;" ";MOD(a1-a2,b);"mod" b PRINT a1;" ";a2;" ";MOD(a1*a2,b);"mod" b a, b, y ax y mod b x a, b d au + bv = d u, v y d y = kd x = ku ax y mod b x 1, x 2 a(x 1 x 2 ) 0 mod b a = a 0 d, b = b 0 d x 1 x 2 b 0 a, b d =1 au + bv =1 u, v x = yu ax y mod b x 1, x 2 x 1 x 2 b 0 x<b a, b

7 7 a>b>0 a b = q r a = b q + r b >r>0 gcd(a, b) =gcd(b, r) b>r>0 gcd(b, r) 0 q a = b q 1 + r 1 b = r 1 q 2 + r 2 r 1 = r 2 q 3 + r 3. r n 1 = r n q n r n n 5n 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, , , , , ,... a n+1 = a n + a n 1 {a n } x 2 x 1=0 u = 1 5, v = a n = ku n + lv n a n+1 = a n + a n 1 a 0 = k + l, a 1 = ku + lv k, l a n a 0, a 1 a n n v n 1+ 5 log 10 = a n n 5! EUCLID1.BAS!! GCD(a,b) INPUT PROMPT "a>b>0 ":a,b PRINT 10 LET q=int(a/b) LET r=mod(a,b) IF r=0 THEN GOTO 30 ELSE GOTO PRINT a;"=";b;" ";q;"+";r LET a=b LET b=r GOTO PRINT a;" ";b;" ";q r =

832040,... a n+1 = a n + a n 1 {a n } x 2 x 1=0 u = 1 5, v = 1+ 5 2 2 a n = ku n + lv n a n+1 = a n + a n 1 a 0 = k + l, a 1 = ku + lv k, l a n a 0, a 1 a n n v n 1+ 5 log 10 = 2 0.

8 8 a, b au + bv =gcd(a, b) u, v a = b q 1 + r 1, b = r 1 q 2 + r 2 a b q 1 = r 1 b (a b q 1 ) q 2 = r 2, a( 1) + b(1 + q 1 q 2 )=r 2, r 1 = r 2 q 3 + r 3 r 1, r 2 a, b r 3 a, b. r n a, b! EUCLID2.BAS!! ax+by=gcd(a,b) x,y GCD(a,b) INPUT PROMPT "a>b>0 ":a0,b0 PRINT LET s1=0 LET t1=1 LET q=int(a0/b0) LET r=mod(a0,b0) PRINT a0;"=";b0;" ";q;"+";r LET s2=1 LET t2=-q PRINT "(";s2;") ";a0;" (";t2;") ";b0;" ";r LET a=b0 LET b=r 10 LET q=int(a/b) LET r=mod(a,b) IF r =0 THEN GOTO 30 ELSE GOTO PRINT a;" ";b;" ";q;" ";r LET s3=s1-q*s2 LET t3=t1-q*t2 PRINT "(";s3;") ";a0;" (";t3;") ";b0;" ";r LET a=b LET b=r LET s1=s2 LET t1=t2 LET s2=s3 LET t2=t3 GOTO PRINT a;" ";b;" ";q 7.

! ax+by=gcd(a,b) x,y GCD(a,b) INPUT PROMPT "a>b>0 ":a0,b0 PRINT LET s1=0 LET t1=1 LET q=int(a0/b0) LET r=mod(a0,b0) PRINT a0;"=";b0;" ";q;"+";r LET s2=1 LET t2=-q PRINT

9 a p a p 1 1 mod p a p 1 mod p mod = = ((((((2 2 +1) 2+1) ) 2+1) ) ) 2 2 a = (((((((((((((((a 2 ) 2 a) 2 a) 2 ) 2 ) 2 ) 2 a) 2 a) 2 ) 2 ) 2 a) 2 ) 2 ) 2 a) 2 ) 2 a mod n n 2=q 1 r 1 n r 1, q 1 2=q 2 r 2 n r 2 q m 1 2=q m =1 q m r m 1 r m 2 r 2 r 1! BIN_EXPANSION.BAS! INPUT PROMPT " ":n LET nn$="" nn$ 0 50 LET nn$=str$(mod(n,2)) & nn$ n nn$ nn$ LET n=(n- MOD(n,2))/2 IF n>0 THEN GOTO 50 n>0 50 PRINT nn$ nn$

2 +1) 2+1) 2 4 +1) 2+1) 2 3 +1) 2 3 +1) 2 2 a 90916 = (((((((((((((((a 2 ) 2 a) 2 a) 2 ) 2 ) 2 ) 2 a) 2 a) 2 ) 2 ) 2 a) 2 ) 2 ) 2 a) 2

10 x n mod a TONTHMODP! TO_THE_NTH_MOD_A.BAS! x, n, a x^n mod a DECLARE EXTERNAL FUNCTION TONTHMODP INPUT PROMPT "x^n mod a x, n, a":x,n,a LET nn$="" 50 LET nn$=str$(mod(n,2)) & nn$ LET n=(n- MOD(n,2))/2 IF n>0 THEN GOTO 50 IF PRINT nn$ PRINT TONTHMODP(x,nn$,a) TONTHMODP EXTERNAL FUNCTION TONTHMODP(x,n$,p) LET y=x FOR i=2 TO LEN(n$) LET y=mod(y*y,p) IF n$(i:i)=str$(1) THEN GOTO 100 ELSE GOTO 130 i LET y=mod(x*y,p) GOTO NEXT i LET TONTHMODP=y y TONTHMODP FUNCTION 7.2. TO_THE_NTH_MOD_A.BAS p 2 p 1 mod p,..., 100 p 1 mod p p a p 1 1 mod p a n 1 1 mod n n 7.3. TO_THE_NTH_MOD_A.BAS n 2 n 1 mod n, 3 n 1 mod n, 5 n 1 mod n, 7 n 1 mod n, 11 n 1 mod n 2, 3, 5, 7, 11

GOTO 50 IF PRINT nn$ PRINT TONTHMODP(x,nn$,a) TONTHMODP EXTERNAL FUNCTION TONTHMODP(x,n$,p) LET y=x FOR i=2 TO LEN(n$) LET y=mod(y*y,p) IF n$(i:i)=str$(1) THEN GOTO 100

11 r r , 3, 5, 7, A, B,...!MOJI2SUJI.BAS! INPUT a$ DIM b(len(a$)) FOR k =1 TO LEN(a$) LET b(k)=ord(a$(k:k)) PRINT b(k);","; NEXT k PRINT DIM c$(len(a$)) FOR k =1 TO LEN(a$) LET c$(k)=chr$(b(k)) PRINT c$(k); NEXT k p, q pq a p, q a (p 1)(q 1) 1 mod pq p, q, a =2,..., 100

12 p, q n = pq (p 1)(q 1) e d ed =1 mod(p 1)(q 1) n, e p,q d n a 1, a 2,..., a k b 1 (a 1 ) e mod n, b 2 (a 2 ) e mod n,...,b k (a k ) e mod n b 1, b 2,...,b k b 1, b 2,..., b k c 1 (b 1 ) d mod n, c 2 (b 2 ) d mod n,...,c k (b k ) d mod n c i (b i ) d ((a i ) e ) d (a i ) ed a i c 1, c 2,...,c k a 1, a 2,...,a k p, q n = pq e EUCLID2.BAS ed+(p 1)(q 1)r =1 d mod (p 1)(q 1) ANGOU.BAS p, q, n, e, d a$!angou.bas! DECLARE EXTERNAL FUNCTION BIN_EXP$ DECLARE EXTERNAL FUNCTION TONTHMODP LET p=13 LET q=17 LET e=7 LET d=55 LET n=p*q PRINT "n=";n; "e=";e LET a$="i love you." PRINT a$ DIM b(len(a$)) DIM c(len(a$))

..,a k 8.4.. 5.2 p, q n = pq e EUCLID2.BAS ed+(p 1)(q 1)r =1 d mod (p 1)(q 1) ANGOU.BAS p, q, n, e, d a$!angou.bas!

13 13 DIM f(len(a$)) FOR k =1 TO LEN(a$) LET b(k)=ord(a$(k:k)) PRINT b(k);","; NEXT k PRINT LET e$=bin_exp$(e) PRINT e$ FOR k=1 TO LEN(a$) LET c(k)=tonthmodp(b(k),e$,n) PRINT c(k);","; NEXT k PRINT LET d$=bin_exp$(d) PRINT d$ FOR k=1 TO LEN(a$) LET f(k)=tonthmodp(c(k),d$,n) PRINT f(k);","; NEXT k PRINT LET g$="" FOR k=1 TO LEN(a$) LET g$=g$ & CHR$(f(k)) NEXT k PRINT g$ EXTERNAL FUNCTION BIN_EXP$(n) LET nn$="" 50 LET nn$=str$(mod(n,2)) & nn$ LET n=(n- MOD(n,2))/2 IF n>0 THEN GOTO 50 LET BIN_EXP$=nn$ FUNCTION EXTERNAL FUNCTION TONTHMODP(x,n$,p) LET y=x FOR i=2 TO LEN(n$) LET y=mod(y*y,p) IF n$(i:i)=str$(1) THEN GOTO 100 ELSE GOTO LET y=mod(x*y,p) GOTO 130

LET g$=g$ & CHR$(f(k)) NEXT k PRINT g$ EXTERNAL FUNCTION BIN_EXP$(n) LET nn$="" 50 LET nn$=str$(mod(n,2)) & nn$ LET n=(n- MOD(n,2))/2 IF n>0 THEN GOTO 50 LET

14 NEXT i LET TONTHMODP=y FUNCTION n, e

Microsoft Word - 触ってみよう、Maximaに2.doc

Microsoft Word - 触ってみよう、Maximaに2.doc i i e! ( x +1) 2 3 ( 2x + 3)! ( x + 1) 3 ( a + b) 5 2 2 2 2! 3! 5! 7 2 x! 3x! 1 = 0 ",! " >!!! # 2x + 4y = 30 "! x + y = 12 sin x lim x!0 x x n! # $ & 1 lim 1 + ('% " n 1 1 lim lim x!+0 x x"!0 x log x