C說話的數字游戲算法效力成績商量實例。本站提示廣大學習愛好者:(C說話的數字游戲算法效力成績商量實例)文章只能為提供參考,不一定能成為您想要的結果。以下是C說話的數字游戲算法效力成績商量實例正文
比來做了如許一個標題,感到挺風趣~標題以下:
成績描寫
Winder 比來在玩一個數字游戲,該游戲是在一個n*m 的網格長進行的,每一個格子上有 一個數字,代表這個格子的數值。玩家須要從網格的左上角的格子走到右下角的格子,每次 只能向右或許向下走,而且不克不及回頭。玩家每經由一個格子可以選擇分值能否加上該格子的 數值,每次游戲的初始分數都是0。
Winder 想曉得在每場游戲,他最多可以或許獲得若干分值。然則,Winder 很懶,所以你必 須幫他來完成這件事。
數據輸出
輸出第一行兩個正整數N 和M(0<N、M<=15)。 接上去有N 行,每行M 個整數。
數據輸入
輸入一行一個整數,表現該場游戲能獲得的最高分數sum。(包管sum 在32 位整數規模 內)。
下面這個成績就是numberGame,斟酌到每步都有且只要向右和向左兩個選擇,故用遞歸算法會很便利,代碼以下:
#include<stdio.h>
#include<iostream>
#include<windows.h>
#pragma comment(lib,"winmm.lib")
using namespace std;
int j=0;
int go(int kc,int *Ac,int wc,int nc)
{
if(kc>=j) return wc;
if(kc<j)
{
if((kc+1)%5==0)
return go(kc+nc,Ac,Ac[kc]+wc,nc);
else
return go(kc+1,Ac,Ac[kc]+wc,nc)>go(kc+nc,Ac,Ac[kc]+wc,nc)?go(kc+1,Ac,Ac[kc]+wc,nc):go(kc+nc,Ac,Ac[kc]+wc,nc);
}
}
void main()
{
int m,n;
DWORD t1, t2;
cin>>m>>n;
int *A,i,w=0;
A=new int [m*n];
for(i=0;i<m*n;i++)
{
if(i!=0&&i%n==0)cout<<endl;
cin>>A[i];
}
j=m*n;
t1=timeGetTime();
int max=go(0,A,w,n);
cout<<max;
t2=timeGetTime();
cout<<"the time it takes:"<<t2-t1;
}
代碼履行時光為46MS,因為最年夜權值途徑上每一個節點的先驅只能是其上方的節點或其右邊的節點(最左的節點除外),故可用一個一維數組存儲每一個節點先驅的最年夜權值,代碼以下:
#include<stdio.h>
int i,j,dp[16],n,m,v;
void main(){
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=1;j<=m;j++){
scanf("%d",&v);
if(dp[j]<dp[j-1])dp[j] = dp[j-1];
dp[j]+= v>0?v:0;
}
printf("%d\n",dp[m]);
}
此代碼用了相似迭代的算法,代碼履行時光為30MS,可知此代碼效力比下面的代碼效力高,而且代碼要比前者簡略的多。