C語言的數(shù)字游戲算法效率問題探討實例
更新時間：2014年04月28日 08:59:35 作者：
這篇文章主要介紹了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ù)范圍 內(nèi)）。
上面這個問題就是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;
}
#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，由于最大權(quán)值路徑上每個節(jié)點的前驅(qū)只能是其上方的節(jié)點或其左邊的節(jié)點（最左的節(jié)點除外），故可用一個一維數(shù)組存儲每個節(jié)點前驅(qū)的最大權(quán)值，代碼如下：
復制代碼 代碼如下:
#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，可知此代碼效率比上面的代碼效率高，并且代碼要比前者簡單的多。
相關(guān)文章
這篇文章主要介紹了c++模擬實現(xiàn)string類詳情，string表示可變長的字符序列，使用string類型必須首先包含string頭文件。作為標準庫的一部分，string定義在命名空間std中，下面進入文章一起看看詳細內(nèi)容吧2022-01-01
這篇文章主要介紹了C/C++中組合的詳解及其作用介紹，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
本文給大家分享的是2則使用C語言控制臺編寫的2048小游戲，各有優(yōu)劣，小伙伴們對比著參考下吧。2015-03-03
這篇文章主要介紹了C++中的6種構(gòu)造函數(shù)的相關(guān)資料,C++中構(gòu)造函數(shù)用于類對象初始化,類型包括默認構(gòu)造函數(shù)、參數(shù)化構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)等,默認構(gòu)造函數(shù)通常不需要參數(shù),編譯器會自動生成,除非存在其他構(gòu)造函數(shù),需要的朋友可以參考下2024-10-10
在C語言中g(shù)etchar的使用方法和讀取規(guī)則講解
getchar中文意思是獲取字符，getchar函數(shù)從標準輸入輸出里讀取下一個字符，返回類型為int整形，返回用戶輸入的ASCII碼值，如果到達文件末尾或者出錯返回EOF，這篇文章主要介紹了在C語言中g(shù)etchar的使用方法和讀取規(guī)則，需要的朋友可以參考下2022-12-12
這篇文章主要為大家詳細介紹了C語言用函數(shù)實現(xiàn)反彈球消磚塊，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-05-05
在C語言中,int?類型的大小通常是根據(jù)系統(tǒng)架構(gòu)來決定的,在大多數(shù)現(xiàn)代系統(tǒng)上,int?通常是32位的,在C語言中,獲取int類型的最大值有幾種不同的方法,下面,我們將討論兩種方法：使用標準庫函數(shù)和使用算法,需要的朋友可以參考下2024-06-06
今天小編就為大家分享一篇關(guān)于整型數(shù)據(jù)在內(nèi)存中存儲方式的講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-02-02
makefile如何調(diào)用靜態(tài)庫的方法實現(xiàn)
這篇文章主要介紹了makefile如何調(diào)用靜態(tài)庫的方法實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12
XML文件可以用來存儲項目中的數(shù)據(jù),它相當于一個簡單的數(shù)據(jù)庫,下面這篇文章主要給大家介紹了關(guān)于Qt讀寫XML文件(含源碼+注釋)的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-10-10