( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1

Size: px

Start display at page:

Download "( ) ( ) 30 ( ) 27 [1] p LIFO(last in first out, ) (push) (pup) 1"

まいかかつもと
5 years ago
Views:

1 () () 30 () 27 [1] p LIFO(last in first out, ) (push) (pup) 1

2 1: List 4-1(p.100) stack[] stack top 1 2 (push) (pop) 1 2 void stack push(double val) val stack top 1 double stack pop(void) stack top 1 1: 1 #define STACK MAX / d o u b l e / 4 double s t a c k [STACK MAX ] ; 5 / / 6 int s t a c k t o p =0; 7 8 / push / 9 void s t a c k p u s h ( double v a l ) 10 { 11 i f ( s t a c k t o p==stack MAX) 12 { 13 / / 14 p r i n t f ( : ( Stack o v e r f l o w )\ n ) ; 1 2

3 15 e x i t (EXIT FAILURE ) ; 16 } 17 else 18 { 19 / / 20 s t a c k [ s t a c k t o p ]= v a l ; 21 ++s t a c k t o p ; 22 } 23 } / pop / 26 double stack pop ( void ) 27 { 28 i f ( s t a c k t o p ==0) 29 { 30 / / 31 p r i n t f ( : p o p 32 ( Stack underflow )\ n ) ; 33 e x i t (EXIT FAILURE ) ; 34 return 0 ; 35 } 36 else 37 { 38 / / 39 s t a c k t o p ; 40 return s t a c k [ s t a c k t o p ] ; 41 } 42 } (queue) queue 2 FIFO(first in first out, ) 2: FIFO 3

4 3 3: List 4-4(p ) queue[] queue[] queue first queue last void enqueue(int val) val queue last 1 () int dequeue(void) queue first 1 () QUEUE EMPTY 2: 1 #define QUEUE MAX 5+1 / +1 / 2 #define QUEUE EMPTY 1 3 4

5 4 / / 5 int queue [QUEUE MAX] ; 6 / / 7 int q u e u e f i r s t =0; 8 / / 9 int q u e u e l a s t =0; / / 12 void enqueue ( int v a l ) 13 { 14 / l a s t f i r s t / 15 i f ( ( q u e u e l a s t +1)%QUEUE MAX ==q u e u e f i r s t ) 16 { 17 / / 18 p r i n t f ( \n ) ; 19 } 20 else 21 { 22 / / 23 queue [ q u e u e l a s t ]= v a l ; 24 / q u e u e l a s t 1 25 / 26 q u e u e l a s t =( q u e u e l a s t +1)%QUEUE MAX; 27 } 28 } / / 31 int dequeue ( void ) 32 { 33 int r e t ; i f ( q u e u e f i r s t==q u e u e l a s t ) 36 { 37 / 1 / 38 return QUEUE EMPTY; 39 } 40 else 41 { 42 / / 43 r e t=queue [ q u e u e f i r s t ] ; 44 / / 45 q u e u e f i r s t =( q u e u e f i r s t +1)%QUEUE MAX; 46 return r e t ; 47 } 48 } 2.3 [ 1] [ 2] LIFO? [ 3] PUSH(n) : n POP() : 5

6 PUSH(3) PUSH(5) POP() PUSH(2) PUSH(1) POP() POP() PUSH(1) POP() PUSH(7) [ 4] POP() [ 5] [ 6] FIFO? [ 7] [ 8] ENQ(n) : n DEQ() : ENQ(6) ENQ(2) DEQ() ENQ(7) DEQ() ENQ(3) ENQ(1) ENQ(2) DEQ() DEQ() [ 9] DEQ() (recursive call)! 5 5! = = 120 (1) n n! = n (n 1) (n 2) 2 1 (2) 0! = 1 n! = n (n 1)! (3) 0! = 1 (4) (2) 3 (3) (4) 4 6

7 4 3 (recursive call) C 3: 1 #include <s t d i o. h> 2 3 / ===================================================== / 4 / / 5 / ===================================================== / 6 int k a i j y o ( int n ){ 7 int i, value ; 8 9 value =1; for ( i=n ; i >=1; i ){ 12 value = i ; 13 } return value ; } / ===================================================== / 20 / / 21 / ===================================================== / 22 int main ( ) { 23 int n ; p r i n t f ( \n ) ; 26 s c a n f ( %d,&n ) ; p r i n t f ( %d!=%d\n, n, k a i j y o ( n ) ) ; return 0 ; 31 } 4: 1 #include <s t d i o. h> 2 3 / ===================================================== / 4 / / 5 / ===================================================== / 6 int k a i j y o ( int n ){ 7 8 i f ( n==0){ 9 return 1 ; 7

8 10 } else { 11 return n k a i j y o ( n 1); 12 } } / ===================================================== / 17 / / 18 / ===================================================== / 19 int main ( ) { 20 int n ; p r i n t f ( \n ) ; 23 s c a n f ( %d,&n ) ; p r i n t f ( %d!=%d\n, n, k a i j y o ( n ) ) ; return 0 ; 28 } 3.2 [ 1] () F 7? F k = F k 1 + F k 2 F 0 = 0 F 1 = 1 [ 2] [ 3] n 2 F (n) F (0) = 1 F (n) = F (n) F (n 1) F (n 1) F (n 2) n F (n 1) (n 1) F (n) [ 4] n n n n! n! = n(n 1)(n 2) 2 1 8

9 tree() 1 4 6? 1: (root:) (node:) (leaf:) (branch:) (parent) (child) (brother) 4: E (binary search tree) 2 9

10 ??2 5: (2 ) : 2 ( List 6-1) 1 typedef struct t a g t r e e n o d e 2 { 3 / / 4 int value ; 5 / n o d e / 6 struct t a g t r e e n o d e l e f t ; 7 / n o d e / 8 struct t a g t r e e n o d e r i g h t ; 9 } t r e e n o d e ; List 6-4(p.176) tree_node *tree_root=null; tree node (NULL) 10

11 6: List6-1List [ 1] 2? () () () () [ 2] 2 69,26,36,45,89,65,11,12,14,23,44 [ 3] 2 70,73,67,75,77,66 11

12 2 [ 4] 2 52,46,54 2 [ 5] (rounding error) C () 2 sin x = x x3 3! + x5 5! x7 7! + x9 9! x11 11! + = ( 1) n+1 x 2n 1 (2n 1)! n=1 (5) 12

13 5.2 [a, b] f(x) f(a)f(b) < 0 (6) f(α) = 0 α [a, b] f(a)f(b) < 0 2 a, b(a < b) [a, b] 2 c = (a + b)/2 f(c) f(c)f(a) < 0 b c f(c)f(a) > 0 a c [a, b] b a ε 1/2 6 a left b riht c mid ε epsilon 6: 1 #include <s t d i o. h> 2 #include <math. h> 3 #include <s t d l i b. h> 4 5 double func ( double x ) 6 { 7 return x cos ( x)+ s i n ( x)+exp( x x)+x x x 3; 8 } double BinarySearch ( void ) 12 { 13 double l e f t, mid, r i g h t, e p s i l o n ; e p s i l o n = ; l e f t = 2.0; 18 r i g h t =2.0; while ( f a b s ( r i g h t l e f t )> e p s i l o n ) 13

14 21 { 22 mid=( l e f t+r i g h t ) / 2. 0 ; i f ( func ( l e f t ) func ( mid) >=0.0) 25 l e f t=mid ; 26 else 27 r i g h t=mid ; 28 } 29 return l e f t ; 30 } int main ( void ) 33 { 34 double d ; 35 d=binarysearch ( ) ; 36 p r i n t f ( %l f 37 func ( x )% l f \n, d, func ( d ) ) ; 38 return EXIT SUCCESS ; 39 } 5.3 [ 1] C 3 [ 2] 2 () [1],.. (),

LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP : 1

2007 7 17 2 1 1.1 LIFO(last in first out, ) 1 FIFO(first in first out, ) 2 2 PUSH POP 2 2 5 5 5 1: 1 2 データの追加データの取り出し 5 2 5 2 5 2: 1.2 [1] pp.199 217 2 (binary tree) 2 2.1 (three: ) ( ) 秋田高専校長準学士課程学生