2 okamotoy@uec.ac.jp 2014 10 21 2014 10 29 10:48 ( ) (2) 2014 10 21 1 / 44
( ) 1 (10/7) ( ) (10/14) 2 (10/21) 3 ( ) (10/28) 4 ( ) (11/4) 5 (11/11) 6 (11/18) 7 (11/25) ( ) (2) 2014 10 21 2 / 44
( ) 8 (12/2) 9 (12/9) (12/16) 10 ( ) (1/6) 11 ( ) (1/13) 12 ( ) (1/20) ( ) (1/27) 13 ( ) (2/3) (2/17?) ( ) (2) 2014 10 21 3 / 44
( ) (2) 2014 10 21 4 / 44
1 2 3 ( ) (2) 2014 10 21 5 / 44
(V, E) V E 2 V V 2 V = {1, 2, 3, 4, 5} E = {{1, 2}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}} {2, 5} = {5, 2} ( ) ( ) (2) 2014 10 21 6 / 44
V = {1, 2, 3, 4, 5} E = {{1, 2}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}} 5 4 1 2 3 ( ) (2) 2014 10 21 7 / 44
G = (V, E) V G E G V G E G {u, v} E u, v v e v e u v u v V = {1, 2, 3, 4, 5} E = {{1, 2}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}} 2, 3 {2, 3} 1 5 4 2 {2, 3} 2 3 2 3 ( ) (2) 2014 10 21 8 / 44
1 1 1 3 5 6 2 2 4 6 5 3 4 1 2 3 4 5 6 ( ) (2) 2014 10 21 9 / 44
( ) (2) 2014 10 21 10 / 44
G = (V, E) G I V 2 u, v I {u, v} E ( ) (2) 2014 10 21 11 / 44
( ) 22 ( ) (2) 2014 10 21 12 / 44
22 ( ) (2) 2014 10 21 13 / 44
G = (V, E) v V σ v {0, 1} σ v = 0 v σv = 1 v σ v = 1 v V = ( ) (2) 2014 10 21 14 / 44
P 1 P 2 P 3 P 4 P 5 P n ( ) (2) 2014 10 21 15 / 44
n 1 2 3 4 5 2 3 5 8 13 ( ) (2) 2014 10 21 16 / 44
P 5 2 (A) = P 4 (B) = 2 P 3 + P 5 = P 4 + P 3 ( ) (2) 2014 10 21 17 / 44
P 5 2 (A) = P 4 (B) = 2 P 3 + P 5 = P 4 + P 3 ( ) (2) 2014 10 21 17 / 44
P 5 2 (A) = P 4 (B) = 2 P 3 + P 5 = P 4 + P 3 ( ) (2) 2014 10 21 17 / 44
P 5 2 (A) = P 4 (B) = 2 P 3 + P 5 = P 4 + P 3 ( ) (2) 2014 10 21 17 / 44
P 5 2 (A) = P 4 (B) = 2 P 3 + P 5 = P 4 + P 3 ( ) (2) 2014 10 21 17 / 44
P 5 2 (A) = P 4 (B) = 2 P 3 + P 5 = P 4 + P 3 ( ) (2) 2014 10 21 17 / 44
( ) P n 2 ( n 3) (A) = P n 1 (B) = 2 P n 2 + n 3 P n = P n 1 + P n 2 ( ) (2) 2014 10 21 18 / 44
( ) P n 2 ( n 3) (A) = P n 1 (B) = 2 P n 2 + n 3 P n = P n 1 + P n 2 ( ) (2) 2014 10 21 18 / 44
( ) P n 2 ( n 3) (A) = P n 1 (B) = 2 P n 2 + n 3 P n = P n 1 + P n 2 ( ) (2) 2014 10 21 18 / 44
a n = P n 2 (n = 1 ) a n = 3 (n = 2 ) a n 1 + a n 2 (n 3 ) ( ) (2) 2014 10 21 19 / 44
P n P 2 (G n ) G 1 G 2 G 3 G 4 G 5 G n ( ) (2) 2014 10 21 20 / 44
P n P 2 G n 2 (A) = (B) = 3 +.... G k ( ) (2) 2014 10 21 21 / 44
P n P 2 G n 2 (A) = (B) = 3 +.... G k ( ) (2) 2014 10 21 21 / 44
P n P 2 G n 2 (A) = (B) = 3 +.... G k ( ) (2) 2014 10 21 21 / 44
P n P 2 (H n ) H 1 H 2 H 3 H 4 H 5 H n n 2 G n = H n + H n 1 ( ) (2) 2014 10 21 22 / 44
P n P 2 H n 2 (A) = (B) = 2 +.... n 2 H n = G n 1 + H n 1 ( ) (2) 2014 10 21 23 / 44
P n P 2 H n 2 (A) = (B) = 2 +.... n 2 H n = G n 1 + H n 1 ( ) (2) 2014 10 21 23 / 44
P n P 2 H n 2 (A) = (B) = 2 + G n 1.. H n 1.. n 2 H n = G n 1 + H n 1 ( ) (2) 2014 10 21 23 / 44
P n P 2 H n 2 (A) = (B) = 2 + G n 1.. H n 1.. n 2 H n = G n 1 + H n 1 ( ) (2) 2014 10 21 23 / 44
P n P 2 b n = G n c n = H n b n = c n = { 3 (n = 1 ) c n + c n 1 (n 2 ) { 2 (n = 1 ) b n 1 + c n 1 (n 2 ) ( ) (2) 2014 10 21 24 / 44
1 2 3 ( ) (2) 2014 10 21 25 / 44
A 1: def fnct(n) 2: print "a" 3: if n > 2 4: fnct(n-1) 5: fnct(n-2) 6: end 7: end fnct(n) a ( ) (2) 2014 10 21 26 / 44
n a n a n a n a 1 1 11 177 21 21891 31 2692537 2 1 12 287 22 35421 32 4356617 3 3 13 465 23 57313 33 7049155 4 5 14 753 24 92735 34 11405773 5 9 15 1219 25 150049 35 18454929 6 15 16 1973 26 242785 36 29860703 7 25 17 3193 27 392835 37 48315633 8 41 18 5167 28 635621 38 78176337 9 67 19 8361 29 1028457 39 126491971 10 109 20 13529 30 1664079 40 204668309 ( ) (2) 2014 10 21 27 / 44
A 1: def fnct(n) 2: print "a" 3: if n > 2 4: fnct(n-1) 5: fnct(n-2) 6: end 7: end f n = fnct(n) a ( ) (2) 2014 10 21 28 / 44
A 1: def fnct(n) 2: print "a" 3: if n > 2 4: fnct(n-1) 5: fnct(n-2) 6: end 7: end 2 n 1 a 4 5 ( ) (2) 2014 10 21 29 / 44
A 1: def fnct(n) 2: print "a" 3: if n > 2 4: fnct(n-1) 5: fnct(n-2) 6: end 7: end f n = { 1 (n 2 ) 1 + f n 1 + f n 2 (n 3 ) ( ) (2) 2014 10 21 30 / 44
Euclid Euclid 1: def gcd(a, b) # precondition: a >= b 2: print "G" 3: if b == 0 4: return a 5: else 6: gcd(b, a % b) 7: end 8: end a % b = a b gcd(a, b) G ( ) ( ) (2) 2014 10 21 31 / 44
Euclid (1) a b G 14 11 5 143 11 2 1432 11 4 14325 11 5 143259 11 5 1432591 11 5 14325910 11 4 143259106 11 3 1432591067 11 5 14325910676 11 2 143259106765 11 4 1432591067659 11 5 14325910676592 11 5 143259106765923 11 4 ( ) (2) 2014 10 21 32 / 44
Euclid (2) a b G 14 13 3 143 13 2 1432 13 4 14325 13 4 143259 13 4 1432591 13 4 14325910 13 3 143259106 13 4 1432591067 13 5 14325910676 13 4 143259106765 13 7 1432591067659 13 5 14325910676592 13 7 143259106765923 13 6 ( ) (2) 2014 10 21 33 / 44
Euclid Euclid 1: def gcd(a, b) # precondition: a >= b 2: print "G" 3: if b == 0 4: return a 5: else 6: gcd(b, a % b) 7: end 8: end g n = max {gcd(a, b) G } a 1,b n g n = b n g n ( ) (2) 2014 10 21 34 / 44
Euclid a, b 1 a b a a % b 2 a = bq + r ( 0 r < b) a % b = r a b q = a r b r = 1 r b b b > 0 q q 1 a a b r < b 2 2 a a b > r = a bq a b < a 2 2 a r 2 a = 2 ( ) n n n 2 = n 2 ( ) (2) 2014 10 21 35 / 44
Euclid a, b 1 a b a a % b 2 a = bq + r ( 0 r < b) a % b = r a b q = a r b r = 1 r b b b > 0 q q 1 a a b r < b 2 2 a a b > r = a bq a b < a 2 2 a r 2 a = 2 ( ) n n n 2 = n 2 ( ) (2) 2014 10 21 35 / 44
Euclid a, b 1 a b a a % b 2 a = bq + r ( 0 r < b) a % b = r a b q = a r b r = 1 r b b b > 0 q q 1 a a b r < b 2 2 a a b > r = a bq a b < a 2 2 a r 2 a = 2 ( ) n n n 2 = n 2 ( ) (2) 2014 10 21 35 / 44
Euclid a, b 1 a b a a % b 2 a = bq + r ( 0 r < b) a % b = r a b q = a r b r = 1 r b b b > 0 q q 1 a a b r < b 2 2 a a b > r = a bq a b < a 2 2 a r 2 a = 2 ( ) n n n 2 = n 2 ( ) (2) 2014 10 21 35 / 44
Euclid a, b 1 a b a a % b 2 a = bq + r ( 0 r < b) a % b = r a b q = a r b r = 1 r b b b > 0 q q 1 a a b r < b 2 2 a a b > r = a bq a b < a 2 2 a r 2 a = 2 ( ) n n n 2 = n 2 ( ) (2) 2014 10 21 35 / 44
Euclid a, b 1 a b a a % b 2 a = bq + r ( 0 r < b) a % b = r a b q = a r b r = 1 r b b b > 0 q q 1 a a b r < b 2 2 a a b > r = a bq a b < a 2 2 a r 2 a = 2 ( ) n n n 2 = n 2 ( ) (2) 2014 10 21 35 / 44
Euclid Euclid 1: def gcd(a, b) # precondition: a >= b 2: print "G" 3: if b == 0 4: return a 5: else 6: gcd(b, a % b) 7: end 8: end g n = gcd(a, b) G a, b... ( b = n) ( ) (2) 2014 10 21 36 / 44
Euclid (1) g n = gcd(a, b) G = 1 + gcd(b, a % b) G a % b = 0 g n = 2 ( gcd(b, a % b) ) a % b 0 ( ) (2) 2014 10 21 37 / 44
Euclid (1) g n = gcd(a, b) G = 1 + gcd(b, a % b) G a % b = 0 g n = 2 ( gcd(b, a % b) ) a % b 0 ( ) (2) 2014 10 21 37 / 44
Euclid (1) g n = gcd(a, b) G = 1 + gcd(b, a % b) G a % b = 0 g n = 2 ( gcd(b, a % b) ) a % b 0 ( ) (2) 2014 10 21 37 / 44
Euclid (1) g n = gcd(a, b) G = 1 + gcd(b, a % b) G a % b = 0 g n = 2 ( gcd(b, a % b) ) a % b 0 ( ) (2) 2014 10 21 37 / 44
Euclid (1) g n = gcd(a, b) G = 1 + gcd(b, a % b) G a % b = 0 g n = 2 ( gcd(b, a % b) ) a % b 0 ( ) (2) 2014 10 21 37 / 44
Euclid (1) g n = gcd(a, b) G = 1 + gcd(b, a % b) G a % b = 0 g n = 2 ( gcd(b, a % b) ) a % b 0 ( ) (2) 2014 10 21 37 / 44
Euclid (2) g n = gcd(a, b) G = 1 + gcd(b, a % b) G = 2 + 2 + gcd(a % b, b % (a % b)) G max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 n 1 g n 2 + g n/2 { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2014 10 21 38 / 44
Euclid (2) g n = gcd(a, b) G = 1 + gcd(b, a % b) G = 2 + 2 + gcd(a % b, b % (a % b)) G max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 n 1 g n 2 + g n/2 { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2014 10 21 38 / 44
Euclid (2) g n = gcd(a, b) G = 1 + gcd(b, a % b) G = 2 + 2 + gcd(a % b, b % (a % b)) G max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 n 1 g n 2 + g n/2 { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2014 10 21 38 / 44
Euclid (2) g n = gcd(a, b) G = 1 + gcd(b, a % b) G = 2 + 2 + gcd(a % b, b % (a % b)) G max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 n 1 g n 2 + g n/2 { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2014 10 21 38 / 44
Euclid (2) g n = gcd(a, b) G = 1 + gcd(b, a % b) G = 2 + 2 + gcd(a % b, b % (a % b)) G max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 n 1 g n 2 + g n/2 { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2014 10 21 38 / 44
Euclid (2) g n = gcd(a, b) G = 1 + gcd(b, a % b) G = 2 + 2 + gcd(a % b, b % (a % b)) G max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 n 1 g n 2 + g n/2 { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2014 10 21 38 / 44
Euclid (2) g n = gcd(a, b) G = 1 + gcd(b, a % b) G = 2 + 2 + gcd(a % b, b % (a % b)) G max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 n 1 g n 2 + g n/2 { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2014 10 21 38 / 44
Euclid (2) g n = gcd(a, b) G = 1 + gcd(b, a % b) G = 2 + 2 + gcd(a % b, b % (a % b)) G max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 n 1 g n 2 + g n/2 { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2014 10 21 38 / 44
Collatz 1: def collatz(n) 2: print n 3: if n % 2 == 0 4: collatz(n/2) 5: else 6: collatz(3*n+1) 7: end 8: end Collatz ( ) n collatz(n) 1 n 20 2 58 (Oliveira e Silva 10) ( ) (2) 2014 10 21 39 / 44
1 2 3 ( ) (2) 2014 10 21 40 / 44
3 3 1 2 3 ( ) (2) 2014 10 21 41 / 44
( ) (2) 2014 10 21 42 / 44
( ) TA OK OK ( ) (2) 2014 10 21 43 / 44
1 2 3 ( ) (2) 2014 10 21 44 / 44