遞歸圖

我理解遞歸的基礎知識，但是當我遇到來自hackerrank的this one這樣的問題時。我很快就對如何處理它感到困惑。遞歸圖

基本上你必須繪製一個分形的ascii樹（由字母Y組成），每層向下減半的Y數。我似乎無法讓我的周圍基本步頭，我可以把它推廣到其他層，如下圖所示：

____________________________________________________________________________________________________ 
__________________1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1_1___________________ 
___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________ 
___________________1___1___1___1___1___1___1___1___1___1___1___1___1___1___1___1____________________ 
____________________1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____1_1_____________________ 
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________ 
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________ 
_____________________1_______1_______1_______1_______1_______1_______1_______1______________________ 
______________________1_____1_________1_____1_________1_____1_________1_____1_______________________ 
_______________________1___1___________1___1___________1___1___________1___1________________________ 
________________________1_1_____________1_1_____________1_1_____________1_1_________________________ 
_________________________1_______________1_______________1_______________1__________________________ 
_________________________1_______________1_______________1_______________1__________________________ 
_________________________1_______________1_______________1_______________1__________________________ 
_________________________1_______________1_______________1_______________1__________________________ 
_________________________1_______________1_______________1_______________1__________________________ 
__________________________1_____________1_________________1_____________1___________________________ 
___________________________1___________1___________________1___________1____________________________ 
____________________________1_________1_____________________1_________1_____________________________ 
_____________________________1_______1_______________________1_______1______________________________ 
______________________________1_____1_________________________1_____1_______________________________ 
_______________________________1___1___________________________1___1________________________________ 
________________________________1_1_____________________________1_1_________________________________ 
_________________________________1_______________________________1__________________________________ 
_________________________________1_______________________________1__________________________________ 
_________________________________1_______________________________1__________________________________ 
_________________________________1_______________________________1__________________________________ 
_________________________________1_______________________________1__________________________________ 
_________________________________1_______________________________1__________________________________ 
_________________________________1_______________________________1__________________________________ 
_________________________________1_______________________________1__________________________________ 
_________________________________1_______________________________1__________________________________ 
__________________________________1_____________________________1___________________________________ 
___________________________________1___________________________1____________________________________ 
____________________________________1_________________________1_____________________________________ 
_____________________________________1_______________________1______________________________________ 
______________________________________1_____________________1_______________________________________ 
_______________________________________1___________________1________________________________________ 
________________________________________1_________________1_________________________________________ 
_________________________________________1_______________1__________________________________________ 
__________________________________________1_____________1___________________________________________ 
___________________________________________1___________1____________________________________________ 
____________________________________________1_________1_____________________________________________ 
_____________________________________________1_______1______________________________________________ 
______________________________________________1_____1_______________________________________________ 
_______________________________________________1___1________________________________________________ 
________________________________________________1_1_________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________ 
_________________________________________________1__________________________________________________

如果任何人都可以給我正確的方向一推，這將不勝感激。

來源

2013-11-25 Bob Templ

您的圖片與您的描述不符。您可以重新解決問題，因爲每個後續行都有Y個字符數的一半。您的第一行將有32個Y字符，用空格分隔。您的下一行將有16個Y字符，位於第一行的Y字符之間。你可以找出其餘的。 –

Ys翻倍，但我重新提出了這個問題，因爲無論如何它會向下生成。 –

我想你需要生成確切的圖像，你能說圖像的大小：lines x cols？ – Pandrei

圖像被以下列方式構造：

Y01 
    Y11 
--------- 
    Y02 
    Y12 
--------- 
    Y04 
    Y14 
--------- 
    Y08 
    Y18 
--------- 
    Y016 
    Y116

Y0x & Y1X用於字母Y：Y0x是枝條和Y1X是將trunc; x是形成字母所需的線的數量

例如， Y02 & Y12 - 2線，形成樹枝和2號線，形成幹線

你可以注意到，還有一個「規則」：當你開始繪製新字母（例如，你從YX2去Yx3）你複製最後一行。

編輯：讓我們假設你有保存在一個矩陣char P[63][100] 我會寫2功能圖紙（不是最佳方法，但你可以優化它） - drawY - 平根據輸入在Y字母 - drawPicutre - 畫出「圖層」Y

drawY(int startPos, int stopPos, int*line, int lvl, int count) 
{ 
    if(lvl>=count) 
    { 
    P[*line][(startPos+(stopPos-startPos))/2] = '1'; 
    P[*line + lvl][(startPos+(stopPos-startPos))/2 +count] = '1'; 
    P[*line + lvl][(startPos+(stopPos-startPos))/2 -count] = '1'; 
    (*line)--; 
    drawY(startPos,stopPos,line,lvl,count+1); 
    } 

} 

int line=63; 
drawY(0,100, &line, 16, 1); // draws the first, and largest Y

你只需要實現第二個函數drawPicture（...），它調用drawY。如果你願意，你可以修改drawY。

來源

2013-11-25 21:34:54 Pandrei

個人我會從底部開始工作我的方式;但這只是一個偏好問題。 – Pandrei

我想，即使知道圖像的結構，我很難將其分解爲遞歸步驟和基本情況。 –

我有點得到你在說什麼，除了我無法通過挑戰的優點來聲明變量，所以矩陣不在表格中。我很好地畫出了整個結構 –

回答

相關問題