2 okamotoy@uec.ac.jp 2015 10 20 2015 10 18 15:29 ( ) (2) 2015 10 20 1 / 45
( ) 1 (10/6) ( ) (10/13) 2 (10/20) 3 ( ) (10/27) (11/3) 4 ( ) (11/10) 5 (11/17) 6 (11/24) 7 (12/1) 8 (12/8) ( ) (2) 2015 10 20 2 / 45
( ) 9 (12/15) (12/22) 10 (1/5) 11 ( ) (1/12) 12 ( ) (1/19) 13 ( ) (1/26) 14 ( ) (2/2) (2/9) (2/16?) ( ) (2) 2015 10 20 3 / 45
( ) (2) 2015 10 20 4 / 45
1 2 3 ( ) (2) 2015 10 20 5 / 45
(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) 2015 10 20 6 / 45
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) 2015 10 20 7 / 45
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) 2015 10 20 8 / 45
1 1 1 3 5 6 2 2 4 6 5 3 4 1 2 3 4 5 6 ( ) (2) 2015 10 20 9 / 45
( ) (2) 2015 10 20 10 / 45
G = (V, E) G I V 2 u, v I {u, v} E ( ) (2) 2015 10 20 11 / 45
( ) 22 ( ) (2) 2015 10 20 12 / 45
22 ( ) (2) 2015 10 20 13 / 45
G = (V, E) v V σ v {0, 1} σ v = 0 v σv = 1 v σ v = 1 v V = ( ) (2) 2015 10 20 14 / 45
P 1 P 2 P 3 P 4 P 5 P n ( ) (2) 2015 10 20 15 / 45
n 1 2 3 4 5 2 3 5 8 13 ( ) (2) 2015 10 20 16 / 45
P 5 2 (A) = P 4 (B) = 2 P 3 { } P 5 = P 4 + P 3 ( ) (2) 2015 10 20 17 / 45
P 5 2 (A) = P 4 (B) = 2 P 3 { } P 5 = P 4 + P 3 ( ) (2) 2015 10 20 17 / 45
P 5 2 (A) = P 4 (B) = 2 P 3 { } P 5 = P 4 + P 3 ( ) (2) 2015 10 20 17 / 45
P 5 2 (A) = P 4 (B) = 2 P 3 { } P 5 = P 4 + P 3 ( ) (2) 2015 10 20 17 / 45
P 5 2 (A) = P 4 (B) = 2 P 3 { } P 5 = P 4 + P 3 ( ) (2) 2015 10 20 17 / 45
P 5 2 (A) = P 4 (B) = 2 P 3 { } P 5 = P 4 + P 3 ( ) (2) 2015 10 20 17 / 45
( ) 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) 2015 10 20 18 / 45
( ) 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) 2015 10 20 18 / 45
( ) 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) 2015 10 20 18 / 45
a n = P n 2 (n = 1 ) a n = 3 (n = 2 ) a n 1 + a n 2 (n 3 ) ( ) (2) 2015 10 20 19 / 45
P n P 2 (G n ) G 1 G 2 G 3 G 4 G 5 G n ( ) (2) 2015 10 20 20 / 45
P n P 2 G n 2 (A) = (B) = 3 { }.... G k ( ) (2) 2015 10 20 21 / 45
P n P 2 G n 2 (A) = (B) = 3 { }.... G k ( ) (2) 2015 10 20 21 / 45
P n P 2 G n 2 (A) = (B) = 3 { }.... G k ( ) (2) 2015 10 20 21 / 45
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) 2015 10 20 22 / 45
P n P 2 H n 2 (A) = (B) = 2 { }.... n 2 H n = G n 1 + H n 1 ( ) (2) 2015 10 20 23 / 45
P n P 2 H n 2 (A) = (B) = 2 { }.... n 2 H n = G n 1 + H n 1 ( ) (2) 2015 10 20 23 / 45
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) 2015 10 20 23 / 45
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) 2015 10 20 23 / 45
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) 2015 10 20 24 / 45
1 2 3 ( ) (2) 2015 10 20 25 / 45
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) 2015 10 20 26 / 45
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) 2015 10 20 27 / 45
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) 2015 10 20 28 / 45
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) 2015 10 20 29 / 45
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) 2015 10 20 30 / 45
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 ( a mod b ) gcd(a, b) G ( ) ( ) (2) 2015 10 20 31 / 45
(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) 2015 10 20 32 / 45
(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) 2015 10 20 33 / 45
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) 2015 10 20 34 / 45
a, b 1 a b a a mod b 2 a = bq + r ( 0 r < b) a mod b = r a b q 1 a a b r < b 2 2 a a a b > r = a bq a b < a = 2 2 2 a r 2 ( ) n n n 2 = n 2 ( ) (2) 2015 10 20 35 / 45
a, b 1 a b a a mod b 2 a = bq + r ( 0 r < b) a mod b = r a b q 1 a a b r < b 2 2 a a a b > r = a bq a b < a = 2 2 2 a r 2 ( ) n n n 2 = n 2 ( ) (2) 2015 10 20 35 / 45
a, b 1 a b a a mod b 2 a = bq + r ( 0 r < b) a mod b = r a b q 1 a a b r < b 2 2 a a a b > r = a bq a b < a = 2 2 2 a r 2 ( ) n n n 2 = n 2 ( ) (2) 2015 10 20 35 / 45
a, b 1 a b a a mod b 2 a = bq + r ( 0 r < b) a mod b = r a b q 1 a a b r < b 2 2 a a a b > r = a bq a b < a = 2 2 2 a r 2 ( ) n n n 2 = n 2 ( ) (2) 2015 10 20 35 / 45
a, b 1 a b a a mod b 2 a = bq + r ( 0 r < b) a mod b = r a b q 1 a a b r < b 2 2 a a a b > r = a bq a b < a = 2 2 2 a r 2 ( ) n n n 2 = n 2 ( ) (2) 2015 10 20 35 / 45
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) 2015 10 20 36 / 45
(1) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G a mod b = 0 g n = 2 ( gcd(b, a mod b) ) a mod b 0 ( ) (2) 2015 10 20 37 / 45
(1) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G a mod b = 0 g n = 2 ( gcd(b, a mod b) ) a mod b 0 ( ) (2) 2015 10 20 37 / 45
(1) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G a mod b = 0 g n = 2 ( gcd(b, a mod b) ) a mod b 0 ( ) (2) 2015 10 20 37 / 45
(1) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G a mod b = 0 g n = 2 ( gcd(b, a mod b) ) a mod b 0 ( ) (2) 2015 10 20 37 / 45
(1) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G a mod b = 0 g n = 2 ( gcd(b, a mod b) ) a mod b 0 ( ) (2) 2015 10 20 37 / 45
(1) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G a mod b = 0 g n = 2 ( gcd(b, a mod b) ) a mod b 0 ( ) (2) 2015 10 20 37 / 45
(2) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G = 2 + gcd(a mod b, b mod (a mod b)) G 2 + max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 b mod (a mod b) b 2 n 1 g n 2 + g n/2 ( ) (2) 2015 10 20 38 / 45
(2) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G = 2 + gcd(a mod b, b mod (a mod b)) G 2 + max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 b mod (a mod b) b 2 n 1 g n 2 + g n/2 ( ) (2) 2015 10 20 38 / 45
(2) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G = 2 + gcd(a mod b, b mod (a mod b)) G 2 + max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 b mod (a mod b) b 2 n 1 g n 2 + g n/2 ( ) (2) 2015 10 20 38 / 45
(2) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G = 2 + gcd(a mod b, b mod (a mod b)) G 2 + max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 b mod (a mod b) b 2 n 1 g n 2 + g n/2 ( ) (2) 2015 10 20 38 / 45
(2) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G = 2 + gcd(a mod b, b mod (a mod b)) G 2 + max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 b mod (a mod b) b 2 n 1 g n 2 + g n/2 ( ) (2) 2015 10 20 38 / 45
(2) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G = 2 + gcd(a mod b, b mod (a mod b)) G 2 + max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 b mod (a mod b) b 2 n 1 g n 2 + g n/2 ( ) (2) 2015 10 20 38 / 45
(2) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G = 2 + gcd(a mod b, b mod (a mod b)) G 2 + max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 b mod (a mod b) b 2 n 1 g n 2 + g n/2 ( ) (2) 2015 10 20 38 / 45
(2) g n = gcd(a, b) G = 1 + gcd(b, a mod b) G = 2 + gcd(a mod b, b mod (a mod b)) G 2 + max a 1,b b/2 {gcd(a, b ) G } = 2 + g b/2 = 2 + g n/2 b mod (a mod b) b 2 n 1 g n 2 + g n/2 ( ) (2) 2015 10 20 38 / 45
( ) ( ) { = 1 n = 0 g n 2 + g n/2 n 1 ( ) (2) 2015 10 20 39 / 45
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 ( ) n collatz(n) 1 n 20 2 58 (Oliveira e Silva 10) ( ) (2) 2015 10 20 40 / 45
1 2 3 ( ) (2) 2015 10 20 41 / 45
3 3 1 2 3 ( ) (2) 2015 10 20 42 / 45
( ) (2) 2015 10 20 43 / 45
( ) TA OK OK ( ) (2) 2015 10 20 44 / 45
1 2 3 ( ) (2) 2015 10 20 45 / 45