Re: [問題] 新手遞回問題

[tropical72 (藍影)]

※ 引述《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 都化掉應不是問題。

→ pigcat1315:丟進去是因為  我有先用陣列紀錄灰階值
→ tropical72:有點好奇的是,即使紀錄了YMean/Gray,是否先算其 x,y 頂
→ tropical72:點,再做RSTA方便些? (也可能有其它實際問題我沒考量..)
→ pigcat1315:t大是指先求出RSAT 所的點有哪些在去求值嗎?
→ pigcat1315:如果是這樣也得紀錄 每個x y 吧@@
我疑問是，要求 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
推 pigcat1315:先感謝大大~ 我當初想法是想說能一起處理
推 pigcat1315:然後下面 if(gray[i][j] > ymean_value) 不懂你是指?
那個只是要表達 , recursive 裡面可以簡單就盡量簡單 ,
沒必要  非再綁一個 array 不可。

→ pigcat1315:我是想找出灰階bmp的RSAT值 所以每個點的值不一定為1
→ pigcat1315:所以不能只知道~有幾個點而是要知道他的座標或加的時候
→ pigcat1315:就把灰階值加入~所以才會想說讀入陣列
既如此 , 真的要改的也只有 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 倒是「該」研究的地方，也值得討論...

推 pigcat1315:話說這樣I函式也要丟gray陣列進去才知道阿~沒理解錯吧
→ tropical72:所以我 gray[][] 才用 global 啊..Orz...
你硬要這樣改也行

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)
推 pigcat1315:QQ 恩謝謝  我也在考慮成本時間問題 繼續研究