Re: [問題] 新手遞回問題
※ 引述《pigcat1315 (還是朋友?)》之銘言：
恕刪。
可能我對於你的問題沒很明確了解，只是很自然看完這篇 #1EGxyjJ1 (Prob_Solve) 後
認為你可能是要實做 RSTA，LPH66 版神說明後，整理一下幾個基本規則
1. R(x , y) = R(x-1, y-1)+R(x+1, y-1) - R(x, y-2) + I(x, y) + I(x, y-1)
2. R(-1, y) = R(0, y-1)
3. R(w , y) = R(w-1, y-1)
*4. I(x , y) = 1 , if (x>=0 and x<w) and (y>=0 and y<h)
I(x , y) = 0 , otherwise
所以才疑惑，若是實做 RSTA ，只要給一個頂點，就可求得 45 度角切出去的面積，
好奇的是為何要用 array 做紀錄？
程式碼大概就這樣
--------
#include <iostream>
#define W 200 /* define by yourself */
#define H 200 /* define by yourself */
int I(int x, int y){ return (x>=0 && x<W && y>=0 && y<H); }
int R(int x, int y)
{
if(y<0 || y>=H) return 0;
else if(x==-1) return R(0, y-1); /* R(-1,y) = R(0,y-1) */
else if(x==W) return (x-1, y-1);
else return R(x-1, y-1)+R(x+1, y-1) - R(x, y-2) + I(x, y) + I(x, y-1);
}
int main()
{
std::cout << "R(2,2) = " << R(2,2) << '\n'; /* output 9*/
std::cout << "R(0,2) = " << R(0,2) << '\n'; /* output 6 */
return 0;
}
這裡 recursive 效率應不好，可把整個 recursive 都化掉應不是問題。
→
08/12 03:14,
08/12 03:14
→
08/12 03:40,
08/12 03:40
→
08/12 03:40,
08/12 03:40
→
08/12 03:49,
08/12 03:49
→
08/12 03:51,
08/12 03:51
我疑問是，要求 RSTA ，只會用到一個 x, 一個 y, 這似乎和存 gray 之陣列無關,
分開處理應會較佳。分開處理「可能」是長這樣
int i, j, sum=0;
for(i=0; i!=W; ++i){
for(j=0; j!=H; ++j){
if(gray[i][j] > ymean_value) /* some condition. */
sum+=R(i,j);
}
}
: int main (void)
: {
: int a=2,b=2;
: sum(a,b);
: system("pause");
: return 0;
: }
: void sum(int a,int b)
: {
: int s;
: if(a==0&&b==0)
: {
: s=1;
: }
: else
: {
: sum(a-1,b-1);
: }
: cout<<s<<endl;
: }
第一步是, 該學會排版。recursive 可能不熟, 一方面也有邏輯錯誤，
你的程式，若於 main 中以 sum(x,y) , 其中 x!=y 呼叫時，將永遠不會有結果
( 可能會有其他結果吧 -
stack overflow, 記憶體於 0x???????? 讀寫發生錯誤,
請洽您的工作管理員。 )
猜你要的東西已經在上面, 這裡便不再修改這段。
--
When I saw the turth of love,
I feel the pain which the world brings to me.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.78.41
推
08/12 12:48, , 1F
08/12 12:48, 1F
推
08/12 13:01, , 2F
08/12 13:01, 2F
那個只是要表達 , recursive 裡面可以簡單就盡量簡單 ,
沒必要 非再綁一個 array 不可。
→
08/12 13:03, , 3F
08/12 13:03, 3F
→
08/12 13:05, , 4F
08/12 13:05, 4F
→
08/12 13:06, , 5F
08/12 13:06, 5F
既如此 , 真的要改的也只有 I(int x, int y) 而已 , 「可能」長這樣
#define W 200 /* define by yourself */
#define H 200 /* define by yourself */
double gray[W][H];
double I(int x, int y)
{
if (x>=0 && x<W && y>=0 && y<H) return gray[x][y];
else return 0.0;
}
double R(int x, int y)
{
/* 其它都一樣 */
}
int main()
{
/* 初始化 gray,by yourself */
for(int i=0, srand(0); i!=W; ++i)
for(int j=0; j!=H; ++j)
gray[i][j] = (double)rand() / RAND_MAX;
/* 做你要做的事 */
return 0;
}
硬要夾 array (pointer) 也行，
但認為真的還沒那必要，細節部份再自己刻，畢竟該怎麼做你比我清楚。
題外話，怎麼改成 non-recursive 倒是「該」研究的地方，也值得討論...
推
08/12 14:56, , 6F
08/12 14:56, 6F
→
08/12 15:12, , 7F
08/12 15:12, 7F
你硬要這樣改也行
double I(int x, int y, double (*gray)[H])
{
if (x>=0 && x<W && y>=0 && y<H) return gray[x][y];
else return 0.0;
}
double R(int x, int y, double (*gray)[H])
{
if(y<0 || y>=H) return 0;
else if(x==-1) return R(0, y-1, gray); /* R(-1,y) = R(0,y-1) */
else if(x==W) return R(x-1, y-1, gray);
else return R(x-1, y-1, gray) + R(x+1, y-1, gray) - R(x, y-2, gray) \
+ I(x , y, gray) + I( x, y-1, gray);
}
int main()
{
double gray[W][H];
/* do something */
}
只是認為 recursive 使用 stack param 之成本代價太高，
所以才用 global variable。
卡在這裡，不如從已出來的版本繼續下去，
現在鑽 recursive 牛角，你的時間上可能不太適合。
※ 編輯: tropical72 來自: 180.177.78.41 (08/12 15:25)
推
08/12 15:34, , 8F
08/12 15:34, 8F
討論串 (同標題文章)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
