［改訂新版］C言語による標準アルゴリズム事典

Size: px

Start display at page:

Download "［改訂新版］C言語による標準アルゴリズム事典"

略慎
7 years ago
Views:

1 iii C 1991 SEND + MORE = MONEY C Java PC-9800 C BMP SVG EPS BMPSVG WindowsMacLinux Web

2 iv int main() int main(void) EXIT_SUCCESS 0 algo-c TEX TEX PDF PDF CTP Computer Modern Palatino Inconsolata

3 v AZ a[0..n-1] a[0] a[n-1] \ Y= (1101) O(n 2 ) n 2 O x x C floor(x) x x C ceil(x) : 3.14 = = 4 x mod y x y : mod 3 = 2 max(... ) min(... ) : max(35, 97, 12) = 97min(35, 97, 12) = 12

5 1 exchange of values ab a = b; b = a; /*! */ temp temp = a; a = b; b = temp; b ^= a; a ^= b; b ^= a; a a = 0 (a b) c = a (b c) b = a - b; a -= b; b += a; b = 0 b = a / b; a /= b; b *= a; RubyPythonJulia a,b = b,a swap.c swap(&x, &y); & int xy 1 void swap(int *x, int *y) 2 { 3 int temp; 4 5 temp = *x; *x = *y; *y = temp; 6 } error detecting code 97 1

6 2 96/ [4] Luhn = = 9 Damm [5] ISBN CRC luhn.c Luhn 1 #include <stdio.h> 2 #include <string.h> 3 4 int main(void) 5 { 6 char *s = " "; /* */ 7 int i, d, w = 1, t = 0; 8 9 for (i = strlen(s) - 1; i >= 0; i--) { 10 d = w * (s[i] - '0'); 11 if (d > 9) d -= 9; 12 t += d; 13 w = 3 - w; 14 } 15 if (t % 10 == 0) printf("\n"); else printf("\n"); 16 return 0; 17 } [1] Benjamin Arazi. A Commonsense Approach to the Theory of Error Correcting Codes. MIT Press, [2] Richard W. Hamming. Coding and Information Theory. Prentice Hall, second edition [3] W. Wesley Peterson and E. J. Weldon, Jr. Error-Correcting Codes. MIT Press, second edition [4] W. Wesley Peterson. Communications of the ACM, 34(12): , December [5] H. Michael Damm. Discrete Mathematics, 307(6): (2007).

7 3 algorithm 9 al-khwārizmī cryptosystem plaintext encrypt encryption ciphertext decrypt decryption cryptanalyze cryptanalysis CaesarCaesar cipher IBM 1 HAL +7 PIT Caesar 3 key Caesar k while ((c = getchar())!= EOF) putchar(c ^ k); 2 c k k = c k k (k c) = c 2 0x20 0x7E while ((c = getchar())!= EOF) putchar((k + 0x7E - c) % 0x5F + 0x20); DESData Encryption Standard FEAL [4] AESAdvanced Encryption StandardNTT Camellia

8 4 [1 4] [5 7] GnuPG gpg crypt.c crypt foo bar foo bar bar foo RAND_MAX #include <stdio.h> 2 #include <stdlib.h> 3 int main(int argc, char *argv[]) 4 { 5 int c, r; 6 FILE *infile, *outfile; 7 8 if (argc < 3 argc > 4 9 (infile = fopen(argv[1], "rb")) == NULL 10 (outfile = fopen(argv[2], "wb")) == NULL) { 11 fputs(": crypt infile outfile [key]\n", stderr); 12 return 1; 13 } 14 if (argc == 4) srand(atoi(argv[3])); 15 while ((c = getc(infile))!= EOF) { 16 do { 17 r = rand() / ((RAND_MAX + 1U) / 256); 18 } while (r >= 256); 19 putc(c ^ r, outfile); 20 } 21 return 0; 22 } [1] Jennifer Seberry and Josef Pieprzyk. Cryptography: An Introduction to Computer Security. Prentice Hall, 1989.

9 5 [2] William H. Press, Brian P. Flannery, Saul A. Teukolsky, and William T. Vetterling. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, Numerical Recipes in C 1993 [3] Al Stevens. DES Revisited and the Shaft. Dr. Dobb s Journal, November 1990, , [4] 1990DES FEAL [5] Bruce Schneier. Applied Cryptography. Wiley, [6] 3 SB 2015 [7] 2015https: //herumi.github.io/ango/ stable marriage problem N N M 1 F 1 M 2 F 2 M 1 F 1 F 2 F 2 M 2 M O(N 2 ) Gale Shapley Shapley 2012

10 6 marriage.c N N N 2N N 1,..., N N = > 3 > > 1 > > 2 > > 3 > > 3 > > 1 > 2 1 #include <stdio.h> 2 #include <stdlib.h> 3 #define N 3 /* */ 4 int boy[n+1], girl[n+1][n+1], position[n+1], rank[n+1][n+1]; 5 6 int main(void) 7 { 8 int b, g, r, s, t; 9 10 for (g = 1; g <= N; g++) { /* */ 11 for (r = 1; r <= N; r++) { 12 scanf("%d", &b); rank[g][b] = r; 13 } 14 boy[g] = 0; rank[g][0] = N + 1; /* */ 15 } 16 for (b = 1; b <= N; b++) { /* */ 17 for (r = 1; r <= N; r++) scanf("%d", &girl[b][r]); 18 position[b] = 0; 19 } 20 for (b = 1; b <= N; b++) { 21 s = b; 22 while (s!= 0) { 23 g = girl[s][++position[s]]; 24 if (rank[g][s] < rank[g][boy[g]]) { 25 t = boy[g]; boy[g] = s; s = t; 26 } 27 } 28 } 29 for (g = 1; g <= N; g++) printf(" %d - %d\n", g, boy[g]); 30 return 0; 31 } [1] Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, [2] Donald E. Knuth. Mariages stables et leurs relations avec d autres problèmes combinatoires: Introduction à l analyse mathématique des algorithmes. Les Presses de l Université de Montréal, 1976.

11 7 [3] Robert Sedgewick. Algorithms. Addison Wesley, second edition Pascal C C++ Java fourth edition 2011 Kevin Wayne [4] Niklaus Wirth

C/C++ - 文件IO

C/C++ - 文件IO C/C++ IO Table of contents 1. 2. 3. 4. 1 C ASCII ASCII ASCII 2 10000 00100111 00010000 31H, 30H, 30H, 30H, 30H 1, 0, 0, 0, 0 ASCII 3 4 5 UNIX ANSI C 5 FILE FILE 6 stdio.h typedef struct { int level ;