算法分析實驗一報告

1、實驗報告算法過程設(shè)計.四、程序調(diào)試及結(jié)果（附截圖）源代碼（附源代碼）.一、買驗內(nèi)容描述和功能分析.1.彼岸內(nèi)容描述：突破蝙蝠的包圍，yifenfei來到一處懸崖面前，懸崖彼岸就是前進的方向， 好在現(xiàn)在的yifenfei已經(jīng)學(xué)過御劍術(shù)，可御劍輕松飛過懸崖?，F(xiàn)在的問題是：懸崖中間飛著很多紅，黃，藍三種顏色的珠子，假設(shè)我們把懸崖看成一條長 度為n的線段，線段上的每一單位長度空間都可能飛過紅，黃，藍三種珠子，而yifenfei 必定會在該空間上碰到一種顏色的珠子。如果在連續(xù)3段單位空間碰到的珠子顏色都不一 樣，則yifenfei就會墜落。比如經(jīng)過長度為3的懸崖，碰到的珠子先后為“紅黃藍”，或者“藍紅黃

2、”等類似情況 就會墜落，而如果是“紅黃紅”或者“紅黃黃”等情況則可以安全到達?，F(xiàn)在請問：yifenfei安然抵達彼岸的方法有多少種？輸入：輸入數(shù)據(jù)首先給出一個整數(shù)c,表示測試組數(shù)。然后是c組數(shù)據(jù)，每組包含一個正整數(shù)n (n<40)o輸出：對應(yīng)每組輸入數(shù)據(jù)，請輸出一個整數(shù)，表示yifenfei安然抵達彼岸的方法數(shù)。每組輸出占一行。例如：輸入：2輸出：92 2132 統(tǒng)計問題內(nèi)容描述：在一無限大的二維平面中，我們做如下假設(shè)：1、每次只能移動一格；2、不能向后走(假設(shè)你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向 上走，但是不可以向下走)；3、走過的格子立即塌陷無法再走第二次；求

3、走n步不同的方案數(shù)(2種走法只要有一步不一樣，即被認為是不同的方案)。輸入：首先給出一個正整數(shù)c,表示有c組測試數(shù)據(jù)接下來的c行，每行包含一個整數(shù)n (n<=20),表示要走n步。輸出：請編程輸出走n步的不同方案總數(shù)；每組的輸出占一行。例如：輸入：2輸出：31 72內(nèi)容描述：the3. message decowingcows arc thrilled because they've just learned about encrypting messages they think they will be able to use secret messages to plot

4、meetings with cows on other farms. cows are not known for their intelligence. their encryption method is nothing like des or blowfish or any of those really good secret coding methods. no, they are using a simple substitution cipher.the cows have a decryption key and a secret message help them decod

5、e it. the key looks like this:yi*whsoujgcxqbativndfezmlpkwhich means that an a1 in the secret message really means y； a 'b' in the secret message really means 'r1; a c1 decrypts to and so on. blanks are not encrypted; they are simply kept in place. input text is in upper or lower case, b

6、oth decrypt using the same decryption key, keeping the appropriate case, of course輸入：* line 1: 26 lower case characters representing the decryption key* line 2: as many as 80 characters that are the message to be decoded輸出：* line 1: a single line that is the decoded message .it should have the same

7、length as the second line of input.仞攻口： 輸入：eydbkmiqugjxlvtzpnwohracsfkifq oua zarxa soar bti yaagrj fa xtfgrj輸出： jump the fence when you seeing me coming二、算法過程設(shè)計第一題是一個典型的遞歸問題，通過對開始的幾項附初始值，通 過循環(huán)利用通項公式依次遞歸調(diào)用公式便可以得到第n項的值。重要 的是總結(jié)出通項公式，其通項公式為：ai=ai-l+bi-l;b i =a i-1 *2+b i-1;c i =a i *3+b i *2;第二題也是一個典型的

8、遞歸問題，通過對開始項附初始值，通過 循環(huán)利用通項公式依次遞歸調(diào)用公式便可以得到第n項的值?？偨Y(jié)出 它的通項公式為：a i =2*a i-l+a i-2;第三題是一道加密解密問題，只要知道他的變換規(guī)律就行了。三、程序調(diào)試及結(jié)果（附截圖）.1 彼岸2 統(tǒng)計問題3. message decowingr 八抒印算法設(shè)計與分析實鯊算法分析實-message deco>.冋x|eydbkm iqugjxlvtzpnwohracsfwifq oua zarxa suar bti yaagrj fa xtfgrjump the fence when you seeing me coningmi上1/源

9、代碼（附源代碼）.1 彼岸#include<stdio.h>int main()int c,n,i;_int64 a40=0,3,9; for(i=3;i<40;i+)ai=2*ai-l+ai-2;scanf("%d",&c);while(c)scanf("%d*',&n); printf("%dnh,an);return 0;2 統(tǒng)計問題#include <iostream>using namespace std;int a30;int main()int i,j,k,n,m,t;al = 3;a2

10、 = 7;for (i=3;i<=20;i+)ai = ai-l*2 + ai-2;scanf(h%dh,&t);while (t)scanf("%d",&n);printf(“drr,an);return 0;3. message decowing#include <iostream>#include <cstdio>#include <cstring>using namespace std;int main(int argc, char *argv)char s27j, a100j;int i,j;while(cin»s)memset(a, 'o', sizeof(a);getchar();gets(a);for(i=0; ai !=、o' i+) if