鏈接:
http://poj.grids.cn/practice/2818這其實(shí)就是一個簡單的移位密碼算法題,只是多了個循環(huán)而已,密碼學(xué)里面也指出過循環(huán)運(yùn)算是沒有效果的,所以題目估計(jì)也就考察了這一點(diǎn),如果沒有找出循環(huán)周期,此題會一直超時的...
剛開始,我就直接模擬K次加密,顯然超時了,當(dāng)時還不信了,以為簡單至此。。。
后面我就開始改進(jìn)了,剛開始是把周期計(jì)算和加密放在一起寫了,樣例也過了,但是還是一直錯...
沒辦法再改,我改成把周期求出來,再對加密次數(shù)K取模后,再進(jìn)行運(yùn)算...
好吧,還是一樣wa,后面就變成PE了。。。
最后,這個題經(jīng)過我近2個小時的奮戰(zhàn),終于過了,一共錯了近10次吧...第一次提交是距現(xiàn)在1個多小時前了...
最后發(fā)現(xiàn)錯誤的原因還是換行輸出的地方錯了,題目要求是每一組中間有個空行,我則輸出的是每次計(jì)算后有個空行...
實(shí)在無語...
思維不嚴(yán)謹(jǐn)啊...
代碼:
#include <stdio.h>
#include <string.h>
#define N_MAX 200 + 10
int main()
{
int nN = 0;
int nNArr[N_MAX];//密鑰
int nK = 0;
char szMsg[N_MAX];
char szMsgBckup[N_MAX];//字符串備份
int nCir[N_MAX];//周期
int nMsgLen = 0;
int nPos = 0;
int i, j;
while (scanf("%d", &nN), nN != 0)
{
for (i = 1; i <= nN; ++i)
{
scanf("%d", &nNArr[i]);
}
for (i = 1; i <= nN; ++i)//計(jì)算周期
{
nPos = i;
for (j = 1; ; ++j)
{
nPos = nNArr[nPos];
if (nPos == i)
{
nCir[i] = j;
break;
}
}
}
while (scanf("%d", &nK), nK != 0)
{
getchar();//銷掉空格
gets(szMsg + 1);
nMsgLen = strlen(szMsg + 1);
for (i = nMsgLen; i < nN; ++i)
{
szMsg[1 + i] = ' ';
}
szMsg[1 + nN] = '\0';
strcpy(szMsgBckup + 1, szMsg + 1);
for (i = 1; i <= nN; ++i)
{
nPos = i;
int nTimes = nK % nCir[i];
for (j = 1; j <= nTimes; ++j)
{
nPos = nNArr[nPos];
}
szMsg[nPos] = szMsgBckup[i];
}
printf("%s\n", szMsg + 1);
}
printf("\n");
}
return 0;
}