大阪の子に間違えたメールアドレス教えちゃった・・・orz あ〜あ。 0168デフォルトの名無しさんNGNG そういえば予選のアフィン暗号の解法が分からんっていってた人いる? 016986NGNG ぷぅ〜。。。つかれた。 たのしかったよ。 0170デフォルトの名無しさんNGNG いないのかぁ〜解説しようと思ったのに 0171160NGNG 168さん教えて! ところで言語はなんですか? 017264NGNG>>168 漏れも解説キボンヌ よければBASIC以外で 0173デフォルトの名無しさんNGNG /* アフィン暗号を解くプログラム 入力文字列から this と that の候補を抽出し, それを片っ端から復号してみて this か that になるまで続ける. */ #include <stdio.h> #include <string.h> #include <stdlib.h>
/* 最大文字列長 兼 最大単語数 */ #define MAXWORD 256
/* 入力単語とその長さ */ char *word[MAXWORD]; int n_word;
/* "this" の候補とその長さ */ int n_this; char *this[MAXWORD];
/* "that" の候補とその長さ */ int n_that; char *that[MAXWORD]; 0174デフォルトの名無しさんNGNG /* 文字列s の b文字目からe文字目が全部異なる 文字からできているかどうか */ int all_different(char *a, int b, int e) { int i,j; for (i = b; i < e; i++) { for (j = i+1; j <= e; j++) { if (a[i] == a[j]) return 0; } } return 1; }
/* 4文字全部異なっていれば this の候補 */ #define IS_THIS(a) all_different(a,0,3) /* 最初の3文字が異なり,最初の文字=最後の文字であれば that の候補 */ #define IS_THAT(a) (all_different(a,0,2)&&(a)[0]==(a)[3]) 0175デフォルトの名無しさんNGNG うわ,インデントが消えちゃう 0176デフォルトの名無しさんNGNG /* 単語の読み込み */ void readword() { int i; char buf[MAXWORD];
i = 0; while (i < MAXWORD && scanf("%s",buf) == 1) { word[i++] = strdup(buf); } n_word = i; } 0177デフォルトの名無しさんNGNG /* 入力文字列 in をアフィン暗号で変換 */ void affine(char *in, int len, int alpha, int beta) { int i; for (i = 0; i < len; i++) in[i] = ((in[i]-'a')*alpha+beta)%26+'a'; }
/* 入力文字列をアフィン暗号で変換したら ref になるかどうか */ int affine_test(char *in, int len, int alpha, int beta, char *ref) { char buf[MAXWORD]; strcpy(buf,in); affine(buf,len,alpha,beta); //printf("a=%d b=%d %s -> %s\n",alpha,beta,in,buf); return strcmp(buf,ref)==0; } 0178デフォルトの名無しさんNGNG /* 入力文字列から this と that の候補を抽出 */ void check_input() { int i; for (i = 0; i < n_word; i++) { int len = strlen(word[i]); if (len != 4) continue; if (IS_THIS(word[i])) this[n_this++] = word[i]; else if (IS_THAT(word[i])) that[n_that++] = word[i]; } } 0179デフォルトの名無しさんNGNG /* アフィン暗号を解く */ /* 考えられるすべての *alpha, *beta について入力にアフィン暗号 変換を施し,this または that の候補が複合できたところで止まる. そのときの alpha, beta の値が返される. */ 0180デフォルトの名無しさんNGNG void solve_affine(int *alpha, int *beta) { int i;
/* ここではbetaを振っているが,入力単語の最初の文字を t に変換するbetaはalphaに対して一意に決まるので, それを求めたほうが速く解ける.ここではプログラミングの 時間がなかったので単純な方法を使った. */ for (*beta = 0; *beta < 26; (*beta)++) { for (i = 0; i < n_this; i++) { if (affine_test(this[i],4,*alpha,*beta,"this")) return; } for (i = 0; i < n_that; i++) { if (affine_test(that[i],4,*alpha,*beta,"that")) return; } } } } 0181デフォルトの名無しさんNGNG int main() { int alpha, beta; int i;
readword(); check_input(); solve_affine(&alpha, &beta); //printf("alpha=%d beta=%d\n",alpha,beta); for (i = 0; i < n_word; i++) { affine(word[i],strlen(word[i]),alpha,beta); printf("%s",word[i]); if (i < n_word-1) putchar(' '); } putchar('\n'); return 0; } 0182デフォルトの名無しさんNGNG 以上です. コピペしてオートインデントかけてちょ. 0183デフォルトの名無しさんNGNG 時間が無いときはこのくらいでもいいと思う。