iii C 1991 SEND + MORE = MONEY C 100 2003 Java 2003 27 PC-9800 C BMP SVG EPS BMPSVG WindowsMacLinux Web
iv int main() int main(void) EXIT_SUCCESS 0 https://github.com/okumuralab/ algo-c TEX TEX PDF PDF CTP Computer Modern Palatino Inconsolata 2018 3 28
v AZ a[0..n-1] a[0] a[n-1] \ Y= (1101) 2 2 1101 O(n 2 ) n 2 O x x C floor(x) x x C ceil(x) : 3.14 = 3 3.14 = 4 x mod y x y : 8 3 2 8 mod 3 = 2 max(... ) min(... ) : max(35, 97, 12) = 97min(35, 97, 12) = 12
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
2 96/97 97 0 [4] Luhn 10 1000... 2 10 9 2 18 1 + 8 = 9 9 9 18 9 = 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 = "5555555555554444"; /* */ 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, 1988. [2] Richard W. Hamming. Coding and Information Theory. Prentice Hall, second edition 1986. [3] W. Wesley Peterson and E. J. Weldon, Jr. Error-Correcting Codes. MIT Press, second edition 1972. [4] W. Wesley Peterson. Communications of the ACM, 34(12): 110 113, December 1991. [5] H. Michael Damm. Discrete Mathematics, 307(6): 715 729 (2007).
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 256 1 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
4 [1 4] [5 7] GnuPG gpg crypt.c crypt foo bar 12345 foo bar 12345 1 bar 12345 foo 0 255 RAND_MAX + 1 256 16 18 1 #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.
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, 1988. 228 236 2 1992 Numerical Recipes in C 1993 [3] Al Stevens. DES Revisited and the Shaft. Dr. Dobb s Journal, November 1990, 149 153, 164 166. [4] 1990DES FEAL [5] Bruce Schneier. Applied Cryptography. Wiley, 1993. 2015 [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 1 1 2 O(N 2 ) Gale Shapley Shapley 2012
6 marriage.c N N N 2N N 1,..., N N = 3 2 3 1 1 2 > 3 > 1 2 1 3 2 2 > 1 > 3 3 2 1 3 3 > 2 > 1 1 3 2 1 1 > 3 > 2 2 3 1 2 2 > 3 > 1 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, 1989. [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.
7 [3] Robert Sedgewick. Algorithms. Addison Wesley, second edition 1988. 499 504 Pascal C C++ Java fourth edition 2011 Kevin Wayne [4] Niklaus Wirth 1979168 176