C語言的數(shù)字游戲算法效率問題探討實(shí)例
最近做了這樣一個(gè)題目，感覺挺有趣~題目如下：
問題描述
Winder 最近在玩一個(gè)數(shù)字游戲，該游戲是在一個(gè)n*m 的網(wǎng)格上進(jìn)行的，每個(gè)格子上有 一個(gè)數(shù)字，代表這個(gè)格子的數(shù)值。玩家需要從網(wǎng)格的左上角的格子走到右下角的格子，每次 只能向右或者向下走，并且不能回頭。玩家每經(jīng)過一個(gè)格子可以選擇分值是否加上該格子的 數(shù)值，每次游戲的初始分?jǐn)?shù)都是0。
Winder 想知道在每場游戲，他最多能夠得到多少分值。但是，Winder 很懶，所以你必 須幫他來完成這件事。
數(shù)據(jù)輸入
輸入第一行兩個(gè)正整數(shù)N 和M（0<N、M<=15）。 接下來有N 行，每行M 個(gè)整數(shù)。
數(shù)據(jù)輸出
輸出一行一個(gè)整數(shù)，表示該場游戲能取得的最高分?jǐn)?shù)sum。（保證sum 在32 位整數(shù)范圍 內(nèi)）。
上面這個(gè)問題就是numberGame，考慮到每一步都有且只有向右和向左兩個(gè)選擇，故用遞歸算法會(huì)很方便，代碼如下：
#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í)行時(shí)間為46MS，由于最大權(quán)值路徑上每個(gè)節(jié)點(diǎn)的前驅(qū)只能是其上方的節(jié)點(diǎn)或其左邊的節(jié)點(diǎn)（最左的節(jié)點(diǎn)除外），故可用一個(gè)一維數(shù)組存儲(chǔ)每個(gè)節(jié)點(diǎn)前驅(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í)行時(shí)間為30MS，可知此代碼效率比上面的代碼效率高，并且代碼要比前者簡單的多。
相關(guān)文章
這篇文章主要介紹了c++模擬實(shí)現(xiàn)string類詳情，string表示可變長的字符序列，使用string類型必須首先包含string頭文件。作為標(biāo)準(zhǔn)庫的一部分，string定義在命名空間std中，下面進(jìn)入文章一起看看詳細(xì)內(nèi)容吧2022-01-01
這篇文章主要介紹了C/C++中組合的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-09-09
本文給大家分享的是2則使用C語言控制臺(tái)編寫的2048小游戲，各有優(yōu)劣，小伙伴們對(duì)比著參考下吧。2015-03-03
這篇文章主要介紹了C++中的6種構(gòu)造函數(shù)的相關(guān)資料,C++中構(gòu)造函數(shù)用于類對(duì)象初始化,類型包括默認(rèn)構(gòu)造函數(shù)、參數(shù)化構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)等,默認(rèn)構(gòu)造函數(shù)通常不需要參數(shù),編譯器會(huì)自動(dòng)生成,除非存在其他構(gòu)造函數(shù),需要的朋友可以參考下2024-10-10
在C語言中g(shù)etchar的使用方法和讀取規(guī)則講解
getchar中文意思是獲取字符，getchar函數(shù)從標(biāo)準(zhǔn)輸入輸出里讀取下一個(gè)字符，返回類型為int整形，返回用戶輸入的ASCII碼值，如果到達(dá)文件末尾或者出錯(cuò)返回EOF，這篇文章主要介紹了在C語言中g(shù)etchar的使用方法和讀取規(guī)則，需要的朋友可以參考下2022-12-12
C語言用函數(shù)實(shí)現(xiàn)反彈球消磚塊
這篇文章主要為大家詳細(xì)介紹了C語言用函數(shù)實(shí)現(xiàn)反彈球消磚塊，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
在C語言中,int?類型的大小通常是根據(jù)系統(tǒng)架構(gòu)來決定的,在大多數(shù)現(xiàn)代系統(tǒng)上,int?通常是32位的,在C語言中,獲取int類型的最大值有幾種不同的方法,下面,我們將討論兩種方法：使用標(biāo)準(zhǔn)庫函數(shù)和使用算法,需要的朋友可以參考下2024-06-06
整型數(shù)據(jù)在內(nèi)存中存儲(chǔ)方式的講解
今天小編就為大家分享一篇關(guān)于整型數(shù)據(jù)在內(nèi)存中存儲(chǔ)方式的講解，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-02-02
makefile如何調(diào)用靜態(tài)庫的方法實(shí)現(xiàn)
這篇文章主要介紹了makefile如何調(diào)用靜態(tài)庫的方法實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
XML文件可以用來存儲(chǔ)項(xiàng)目中的數(shù)據(jù),它相當(dāng)于一個(gè)簡單的數(shù)據(jù)庫,下面這篇文章主要給大家介紹了關(guān)于Qt讀寫XML文件(含源碼+注釋)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-10-10