C語言的數(shù)字游戲算法效率問題探討實例
最近做了這樣一個題目,感覺挺有趣~題目如下:
問題描述
Winder 最近在玩一個數(shù)字游戲,該游戲是在一個n*m 的網(wǎng)格上進行的,每個格子上有 一個數(shù)字,代表這個格子的數(shù)值。玩家需要從網(wǎng)格的左上角的格子走到右下角的格子,每次 只能向右或者向下走,并且不能回頭。玩家每經(jīng)過一個格子可以選擇分值是否加上該格子的 數(shù)值,每次游戲的初始分數(shù)都是0。
Winder 想知道在每場游戲,他最多能夠得到多少分值。但是,Winder 很懶,所以你必 須幫他來完成這件事。
數(shù)據(jù)輸入
輸入第一行兩個正整數(shù)N 和M(0<N、M<=15)。 接下來有N 行,每行M 個整數(shù)。
數(shù)據(jù)輸出
輸出一行一個整數(shù),表示該場游戲能取得的最高分數(shù)sum。(保證sum 在32 位整數(shù)范圍 內)。
上面這個問題就是numberGame,考慮到每一步都有且只有向右和向左兩個選擇,故用遞歸算法會很方便,代碼如下:
#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;
}
代碼執(zhí)行時間為46MS,由于最大權值路徑上每個節(jié)點的前驅只能是其上方的節(jié)點或其左邊的節(jié)點(最左的節(jié)點除外),故可用一個一維數(shù)組存儲每個節(jié)點前驅的最大權值,代碼如下:
#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]);
}
此代碼用了類似迭代的算法,代碼執(zhí)行時間為30MS,可知此代碼效率比上面的代碼效率高,并且代碼要比前者簡單的多。
您可能感興趣的文章
- 04-02c語言函數(shù)調用后清空內存 c語言調用函數(shù)刪除字符
- 04-02c語言的正則匹配函數(shù) c語言正則表達式函數(shù)庫
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言中對數(shù)函數(shù)的表達式 c語言中對數(shù)怎么表達
- 04-02c語言用函數(shù)寫分段 用c語言表示分段函數(shù)
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排序法函數(shù)
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段函數(shù)
- 04-02C語言中怎么打出三角函數(shù) c語言中怎么打出三角函數(shù)的值
- 04-02c語言調用函數(shù)求fibo C語言調用函數(shù)求階乘


閱讀排行
本欄相關
- 04-02c語言函數(shù)調用后清空內存 c語言調用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調用函數(shù)求fibo C語言調用函數(shù)求
隨機閱讀
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-10SublimeText編譯C開發(fā)環(huán)境設置
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-11ajax實現(xiàn)頁面的局部加載
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 04-02jquery與jsp,用jquery
- 01-10C#中split用法實例總結
- 01-10delphi制作wav文件的方法
- 08-05織夢dedecms什么時候用欄目交叉功能?