尋找一個遞歸修改的正方形的周長

我有一個邊長爲1的正方形。現在，在每秒之後，每邊L的每個正方形將分裂成每邊L/2的四個正方形。尋找一個遞歸修改的正方形的周長

enter image description here

我所需要的計算所得到的圖中，其中總周長被定義爲在所得到的圖中的所有線段的長度之和的總周長。例如，左側圖像的總周長爲4L，而右側的圖像總長爲6L-4L，內部線段爲2L。

我的代碼：

#include <cmath> 
#include <cstdio> 
#include <vector> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
#define mod 1000000007 

int main() { 



     int s; 
     cin>>s; 
     long long int ans=4; 

     for(int i=1;i<=s;i++) 
      ans+=1<<i; 
      ans=ans%mod; 

     cout<<ans<<endl; 


    return 0; 
}

因爲最終的答案可能無法在64位有符號整數合身，我需要計算的答案模1000000007。

例如0秒後，長度爲4。第二後如圖1所示，長度爲6。 我沒有得到正確的輸出。 PLease幫助

來源

2014-10-07 user4115692

@MikeSeymour因爲長度爲1，和我initally採取ANS = 4 – user4115692 2014-10-07 05:01:10

顯示一個例子你所期望的要顯示，如果該程序是正確的。 – 2014-10-07 05:02:04

@PreetSangha我用這種方法得到錯誤的答案，我正在請求我犯的錯誤 – user4115692 2014-10-07 05:03:25

遞歸求解 - 讓P(L, n)成爲n迭代後得到的圖的「周長」，從LxL開始。那麼，P(L, n+1) = 4*P(L/2,n) - 2*L。另外，由於周長線性，P(L/2, n) = P(L, n)/2，給你P(L,n) = 2*P(L,n-1) - 2*L。用L=1替代並運行你的循環。

int s; 
    cin>>s; 
    long long int ans=4; 

    for(int i=1;i<=s;i++) 
    { 
     ans = 2*(ans-1); 
     ans=ans%mod; 
    }

來源

2014-10-07 05:09:00 Pradhan

我的方法 – user4115692 2014-10-07 05:14:56

@ user4115692有什麼問題，如果遞歸解決了你編碼的問題，那麼問題就出現在'1 << s'中。你應該讓你長久。 – Pradhan 2014-10-07 05:20:15

s秒後的周長將是：4 + 2（2^S-1）所以，

int main() 
{ 
    int s; 
    cout << "Enter Time: "; 
    cin >> s; 
    cout << "Perimeter = " << (4 + 2 * (pow(2, s) - 1)); 
}

來源

2014-10-07 05:24:45 sajas

您有未分割的正方形。當你把這個正方形分成4個相等的正方形時，你基本上會增加一半的初始周長。原始方形的外壁在新的周邊中包含，並增加其內部繪製的兩條線的長度，其中每條線的長度等於正方形的邊。 noOfsqaures = 1; oldSide = 1; //one sqaure of side 1 oldPerimeter = 4*oldSide; loop for the number of seconds newPerimeter = oldPerimeter + 2*oldSide*noOfSquares oldSide = oldSide/2; //for the next iteration oldPermiter = newPermeter //for the next iteration noOfSquares = noOfSquares*4;

來源

2014-10-07 05:27:37 Sinstein

O/P：4（初始值）+ 2 + 4 + 8 + 16 + 32 + ...

我認爲這將有助於你的編碼。如果你需要，我會給你的代碼

for(int i=1;i<=s;i++) 
{ 
    ans+=1<<i; 
}

來源

2014-10-07 05:30:28 user966379

尋找一個遞歸修改的正方形的周長

回答

相關問題