software2-lecture

Size: px

Start display at page:

Download "software2-lecture"

ぜんぺいそめや
3 years ago
Views:

2 ! C!! assert!!!!!

3 ! C!! assert!!!!!

4 !!!! int factorial(int n) { if (n == 0) return 1; } return n * factorial(n - 1);

5 factorial()! factorial(4) 4*6=24 4*factorial(3) 3*2=6 3*factorial(2) 2*1=2 2*factorial(1) 1*1=1 1*factorial(0) if (n == 0) return 1; 1

6 !! Euclid s algorithm!! m n (m n) n m n while int euclid(int m, int n) { int remainder; int euclid(int m, int n) { int remainder = m % n; } while ((remainder = m % n)!= 0) { m = n; n = remainder; } return n; } if (remainder == 0) return n; else return euclid(n, remainder);

7 !!! int factorial(int n) { if (n == 0) return 1; } return n * factorial(n - 1); int euclid(int m, int n) { int remainder = m % n; } if (remainder == 0) return n; else return euclid(n, remainder);

8 ! #include <stdio.h> void test(int *a) { printf( %d\n,(*a)++); test(a); } int main(void) { int a = 0; test(&a); return 0; } ==

9 !! :!!!

10 ! size_t fread(void* data, size_t size, size_t nitems, FILE* fp); size nitems size_t fwrite(void* data, size_t size, size_t nitems, FILE *fp); size nitems 10

11 writebinaryfile.c! 1000 double 2! ->! 1! size_t! 1000! gcc -o writebinaryfile writebinaryfile.c./writebinaryfile data.txt data.dat

12 1! : fread!! malloc!!!! time time./readbinaryfile data.dat

13 ! C!!!assert!!!!

14 !!!!!!!!

15 ! Knapsack Problem!! W nx max v i x i i=1 subject to nx i=1 w i x i apple W, x i 2 {0, 1} 0-1

!! 0 0 0 0 0 0 0 1 2 2 W = 15 4 12 10 4 2 2 0 1 0 10 4

16 !! W =

17 ! $ gcc -Wall -o knapsack knapsack.c!! 10 $./knapsack !! NG

18 main! const (assert ) const int max_items = 100; 100 max number of items

19 ! Itemset *init_itemset(int, int);!! void free_itemset(itemset*)! free! void save_itemset(char *, Itemset*)!! double solve(itemset*, double, int*)!! double search(int, Itemset*, double, int*, double, double)!solve!

20 search()!! i!

21 search() double search(int index, const Itemset *list, double capacity, int *flag,double sum_v, double sum_w) { int max_index = list->number; assert(index >= 0 && sum_v >=0 && sum_w >= 0); if (index == max_index) { for (int i = 0 ; i < max_index ; i++){ printf("%d", flags[i]); } printf(", total_value = %5.1f, total_weight = %5.1f\n", sum_v, sum_w); return sum_v; } i flags[index] = 0; const double v0 = search(index+1, list, capacity, flags, sum_v, sum_w); flags[index] = 1; const double v1 = search(index+1, list, capacity, flags, sum_v + list- >value[index], sum_w + list->weight[index]); } return (v0 > v1)? v0 : v1; "

22 solve()! search()!0!! flags double solve(const Itemset *list, double capacity) { unsigned char *flags = (unsigned char*)calloc(list->number, sizeof(unsigned char)); double max_value = search(0,list,capacity,flags, 0.0, 0.0); free(flags); return max_value; }

23 search O(2^n)

24 main() solve()

25 2 1. knapsack.c - : : search -> - flags

26 DP! DP! [ ]

27 ! C!!!assert!!!!

28 !! A B

29 tsp.c! $ gcc -Wall -o tsp tsp.c lm!!! $./tsp city10seed3.dat!! gencity.c ->

30 tsp.c!!!!city[i]! i (0 i < n)!route[j]! j! route[0] = 0 0!!visited[k]! k

31 tsp.c c 0 c 3 route[0] = 0 route[1] = 2 route[2] = 4 route[3] = 1 route[4] = 3 c 2 c 4 c 1

32 ! O ( n 1)! )

33 ! tsp.c! [ ]! route!!!

34 hill climbing!! !!!!

35 !!!!

36 ! 2 2! 2 ->!! 2!!

37 12/19 1. helloworld.c Hello,World 2. fibo(n) O(log n) 3. knapsack.c 4. 5.

38 ITC-LMS! :! / zip tar.gz!git archive zip!soft nnnnnnnn.zip SOFT NNNNNNNN.tar.gz! NNNNNNNN! J J???????!![ ]![ ] 38

39 !! T, r (0 < r < 1) 1. 2.! exp(d/t)! d = 3. T T rt 4. T 2

40 !!!! T! T!!! T r

Ｃ言語によるアルゴリズムとデータ構造

Ｃ言語によるアルゴリズムとデータ構造 Algorithms and Data Structures in C 4 algorithm List - /* */ #include List - int main(void) { int a, b, c; int max; /* */ Ÿ 3Ÿ 2Ÿ 3 printf(""); printf(""); printf(""); scanf("%d", &a); scanf("%d",