亚洲国产成人久久一区WWW,国产精品久久久久AV福利动漫,蜜臀av性久久久久蜜臀aⅴ

這個題目，我們讓老師鄙視了。。。

Description

Famous Harry Potter,who seemd to be a normal and poor boy,is actually a wizard.Everything changed when he had his birthday of ten years old.A huge man called 'Hagrid' found Harry and lead him to a new world full of magic power.
If you've read this story,you probably know that Harry's parents had left him a lot of gold coins.Hagrid lead Harry to Gringotts(the bank hold up by Goblins). And they stepped into the room which stored the fortune from his father.Harry was astonishing ,coz there were piles of gold coins.
The way of packing these coins by Goblins was really special.Only one coin was on the top,and three coins consisted an triangle were on the next lower layer.The third layer has six coins which were also consisted an triangle,and so on.On the ith layer there was an triangle have i coins each edge(totally i*(i+1)/2).The whole heap seemed just like a pyramid.Goblin still knew the total num of the layers,so it's up you to help Harry to figure out the sum of all the coins.

Input

The input will consist of some cases,each case takes a line with only one integer N( 0 < N < 2^31).It ends with a single 0.

Output

For each test case, output a line contains the number of all the coins, the format like the sample out(2 decimal digits).

Sample Input

1
3
0

Sample Output

1.00E0
1.00E1

Hint

when N=1 ,There is 1 gold coins.
when N=3 ,There is 1+3+6=10 gold coins.

題目很簡單，求Sn=i*(i+1)/2的前n項和，n由題目給出。
平方和公式：1^2+2^2+3^2+...+n^2=n(n+1)(2*n+1)/6 等差求和：1+2+3+...+n=n*(n+1)/2

代碼如下：

#include<stdio.h>

#include<math.h>

int main()

{

double test,sum;

int i;

scanf("%lf",&test);

while(test!=0)

{

sum=((test*(test+1)*(2*test+1))/6+(test*(test+1))/2)/2;

i=0;

while(sum>=10)

{

i++;

sum=sum/10;

}

printf("%.2fE%d\n",sum,i);

scanf("%lf",&test);

}

return 0;

}

posted @ 2010-09-06 10:11 jince 閱讀(485) | 評論 (0) | 編輯收藏

Double Seventh Festival

有時候失去的總比得到的多！

Description

The Double Seventh Festival, on the 7th day of the 7th lunar month, is a traditional festival full of romance. On that day, the God of the Love came to the digital kingdom, and annunciated to the people:

Notification


                             Do you want to know who is your fere? You can find him or her by this means:

                       Please add all the factors of your ID-Card-Number, and you can find this is your fere's

                       ID-Card-Number.

The factors of a numer N is the numbers,they being small than the number N ,and can being divided exactly by the number N.
For example, the number 12 has the factors, such as 1,2,3,4,6.

Input

The fist line is the number T (1 <= T <= 500000), indicated the number of the test cases.
The next T lines, each line has one integer N( 1 <= N <= 500000), meaning the ID-Card-Number.

Output

For each test case, you should output the fere's ID-Card-Number on a line.

Sample Input

Sample Output

1
8
22

      這個題目在我剛開始接觸ACM的時候做出來最有成就的一個！求各因子之和！

代碼如下：

#include<cstdio>
int main()
{
    int i,j,n,m,sum;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        sum=0;
        scanf("%d",&m);
        for(j=1;j*j<=m;j++)
        {
            if(m%j==0)
            {
                sum=sum+j+m/j;
            }
            if(j*j==m)
                sum-=j;
        }
        printf("%d\n",sum-m);
    }
    return 0;
}

posted @ 2010-09-06 09:34 jince 閱讀(1041) | 評論 (0) | 編輯收藏

最大和子段

         下午真的很想睡覺，可是上床，下床好幾次了，都沒睡著，焦慮啊！！可能像我這樣剛畢業的人都會這樣！工資好像還沒發！我問他們，他們說其他人都發了。。。馬上又要交房租了，我想對房東說，我已經打到你卡上了，你沒收到嗎？然后我就去露宿街頭。。。我很勇敢，但是我不傻！

         給定n個整數（可能為負）組成序列a1,a2,...an，求該序列的最大和子段！這個題目有很多解法！！！

         一、窮舉法
         這種方法很容易想到，就不怎么說明了，直接上代碼！
代碼如下：

int MaxSum(int n,int *a,int &besti,int& bestj)

{

int sum=0;

int i,j;

for(i=1;i<=n;i++)

{

int thissum=0;

for(j=i;j<=n;j++)

{

thissum+=a[j];

if(thissum>sum)

{

sum=thissum;

besti=i;

bestj=j;

}

return sum;

}

二、二分法
將數組a[1..n]分成左右的兩段a[1..n/2]和a[n/2+1...n]；最大和字段可能落在左子段，可能落在右子段，也可能落在中間，即一部分在左，一部分在右；對于前面兩種情況可以直接遞歸求解，對于最后這種情況，只要從a[n/2]出發，分別累加左子段和得到一個最大值s1，右子段和得到一個最大值s2，s1+s2可得到一個最優值；然后取三者最優！！
代碼如下：

int MaxSubSum(int *a,int left,int right)

{

int sum=0;

int j,i;

if(left==right) sum=a[left]>0?a[left]:0;

else

{

int center=(left+right)/2;

int leftsum=MaxSubSum(a,left,center);

int rightsum=MaxSubSum(a,center+1,right);

int s1=0;

int lefts=0;

for(i=center;i>=left;i--)

{

lefts+=a[i];

if(lefts>s1)

s1=lefts;

}

int s2=0;

int rights=0;

for(j=center+1;j<=right;j++)

{

rights+=a[j];

if(rights>s2)

s2=rights;

}

sum=s1+s2;

if(sum<leftsum) sum=leftsum;

if(sum<rightsum) sum=rightsum;

}

return sum;

}

其實這個算法先將n大的序列二分置大小為1的序列，然后回溯回去，回溯過程中一直取最優值，實現了信息填充和附帶功能！

          三、動態規劃
         這種算法最簡單，效率也最高，但是不是很容易理解！好的東西常常很難去解釋！
         我個人是這么理解的，假設最大序列是從第一個數開始加的一個子序列，那么我們只要從第一個數一直加，取最大的那個值解釋最優了！當然這只是假設，最大子序列的初始位置可能會在其他地方，這里就有一個舍棄和，和重新累加的問題，假設從1開始加我們得到一個正和，我們就舍棄（當然在這個過程中我們會一直比較最優值，并把它記錄下來），重新累加，顯然，無論后面累加得到一個正和或者負和我們都應該把前面那個舍棄的正和加進去；類似的當從1累加得到非正數時，我們就應該把它這段累加和舍棄，重新開始累加！
代碼如下：

//求一維數組最大和子段不考慮數組全為負的情況

int maxsum(int n,int *a)

{

int sum=0,b=0;

int i;

for(i=1;i<=n;i++)

{

if(b>0)

b+=a[i];

else

b=a[i];

if(b>sum) sum=b;

}

return sum;

}

最終其實會得到一幅以數列為軸的點圖，最高那個就是最大和字段和！

posted @ 2010-09-05 17:29 jince 閱讀(576) | 評論 (2) | 編輯收藏

最長公共子序列

       問題描述：給定序列X={x1,x2,..xn}和Y={y1,y2...ym},求一個Z={z1,z2,..zk}序列是X,Y的最長公共子序列！！

      書上描述的已經十分詳細了，而且容易理解。通過定義c[i][j]用于記錄Xi和Yi的最長公共子序列的長度，從而遞推得到結果。

遞推方程如下：
                 c[i][j]=0,i=0,j=0；    c[i][j]=c[i-1][j-1]+1,xi=yj；     c[i][j]=max(c[i-1][j],c[i][j-1]),xi!=yj；（不知道怎么輸出大括號，悲劇啊！）

代碼如下：

#include<stdio.h>

void LCSLength(int m,int n,char *x,char *y,int c[][100],int b[][100])

{

int i,j;

for(i=1;i<=m;i++) c[i][0]=0; //當i==0或者j==0時，代表其中一個序列為空，c[i][j]當然為0

for(j=1;j<=n;j++) c[0][j]=0;

for(i=1;i<=m;i++) //二重循環

for(j=1;j<=n;j++)

{

if(x[i]==y[j])

{

c[i][j]=c[i-1][j-1]+1;

b[i][j]=1;

}

else

{

if(c[i-1][j]>=c[i][j-1])

{

c[i][j]=c[i-1][j];

b[i][j]=2;

}

else

{

c[i][j]=c[i][j-1];

b[i][j]=3;

}

void LCS(int i,int j,char x[],int b[][100]) //遞歸求得最長子序列

{

if(i==0||b==0)

return;

if(b[i][j]==1)

{

LCS(i-1,j-1,x,b);

printf("%c",x[i]);

}

else if(b[i][j]==2)

LCS(i-1,j,x,b);

else

LCS(i,j-1,x,b);

}

int main()

{

char x[100],y[100];

int i,j;

int c[100][100],b[100][100];

scanf("%s %s",x+1,y+1);

c[0][0]=0;

LCSLength(7,6,x,y,c,b);

for(i=0;i<8;i++)

{

for(j=0;j<7;j++)

{

printf("%d ",c[i][j]);

}

printf("\n");

}

LCS(7,6,x,b);

printf("\n");

return 0;

}

運行結果：

posted @ 2010-09-04 23:17 jince 閱讀(325) | 評論 (0) | 編輯收藏

矩陣相乘

         矩陣相乘問題描述：給定n個矩陣{A1，A2，...，An}，當然A1到An的任意段都是可乘的，求最小相乘次數。例如有三個矩陣維數分別為：10*100，100*2，2*5；若前兩個相乘，再乘第三個，總的相乘次數=10*100*2+10*2*5=2100；若第二個與第三個先相乘，在乘第一個，總相乘次數=100*2*5+10*100*5=5100；顯然，相乘次序會對計算量有很大影響，如果你在學線性代數的時候，寫了一個矩陣相乘的程序，結果跑到同學那里演示的時候，半天沒運行出來，那就尷尬了！！！

             函數調用一般會要傳參，這些參數都是非常有意義。這個題目屬于動態規劃，最重要的一點就是想到一個二維數組m[i][j]，代表矩陣i到矩陣j相乘的最優解，然后就是怎樣給這個有意義的數組置數了，這種數組定義和數組置數若成，則我們要的答案就在m[1][n]中，代表矩陣1到矩陣n相乘的最優解。（如果你很饑渴的想解決這個問題，就直接看代碼吧！！）有人可能會問，為什么會想到這種數組定義，主要有兩個方面：一，學習（高效），看多了自然會想到給數組某種意義，培育一種思想；二、思考與分析，來的緩慢，但是凌駕與學習之上，也是學習的目的，是終極武器，也是基礎武器。。。。

           不扯了，回到主題，很明顯如果只有一個矩陣，相乘次數為零；如果有兩個，直接相乘，若第一個矩陣維數q*p，第二個矩陣維數p*r，相乘次數為q*p*r；三個矩陣相乘，為前兩相乘，再乘第三個，和后兩個先相乘，再乘第一個，取其優者；四個矩陣相乘，設第三個矩陣維數r*t，第四個矩陣t*k，維數min{前三個矩陣最優值+q*t*k，前兩個矩陣最優+后兩個矩陣最優+q*r*k，前一個矩陣最優+后三個矩陣最優+q*p*k}；然后。。。

有人可能會問：我可以算出前一個，前兩個，前三個矩陣相乘的最優，但是我怎么算出后一個，后兩個，后三個相乘的最優呢？
其實這個問題又回到了原點，這就是動態規劃的妙處，顯然我們先求出A1到An的任意段長度為2矩陣的最優（直接相乘），然后可以計算出任意段長度為3矩陣的最優；然后。。。然后我們就想了個m[i][j]出來，記錄我們求的的結果；然后再寫代碼，嘗試思想的準確性，當然我們更多的時候是站在先人的肩膀上做驗證工作。。。

代碼如下（參考教科書）：

#include<iostream>

using namespace std;

void chain(int *p,int n,int m[][7],int s[][7])//p維數數組，m最優乘次數組，s記錄劃分方案

{

int j;

for(int i=1;i<=n;i++)

m[i][i]=0;

for(int r=2;r<=n;r++)

{

for(i=1;i<=n-r+1;i++)

{

j=i+r-1;

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];

s[i][j]=i;

for(int k=i+1;k<j;k++)

{

int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

if(t<m[i][j])

{

m[i][j]=t;

s[i][j]=k;

}

for(i=1;i<=n;i++) //我把它翻過來輸出。。。

{

for(j=n;j>=i;j--)

{

cout<<m[i][j]<<' ';

}

cout<<endl;

}

void Traceback(int i,int j,int s[][7]) //輸出相乘方案

{

if(i==j)

return;

Traceback(i,s[i][j],s);

Traceback(s[i][j]+1,j,s);

cout<<"Multiply A "<<i<<","<<s[i][j];

cout<<" and B "<<(s[i][j]+1)<<","<<j<<endl;

return;

}

int main()

{

int p[7],m[7][7],s[7][7],n;

while(scanf("%d",&n)!=EOF)

{

for(int i=0;i<=n;i++)

{

scanf("%d",&p[i]);

}

chain(p,n,m,s);

Traceback(1,6,s);

}

return 0;

}

p52

測試數據：

30 35 15 5 10 20 25

運行結果：

posted @ 2010-09-04 11:53 jince 閱讀(2536) | 評論 (0) | 編輯收藏

容器

C++ 中vector容器，挺好用的，記錄一下！按照vector容器函數說明測了一下，一一應驗！
代碼如下：

#include<stdio.h>

#include<vector>

#include<iostream>

#include<algorithm>

#include<functional>

using namespace std;

bool cmp(const int &a,const int &b)

{

return a>b;

}

int main()

{

vector<int> v1;

v1.push_back( 0 );

v1.push_back( 1 );

v1.push_back( 2 );

v1.push_back( 3 );

vector<int> v2;

v2.push_back( 5 );

v2.push_back( 6 );

v2.push_back( 7 );

v2.push_back( 8 );

cout << "Before, v2 is: ";

for( vector<int>::size_type i = 0; i < v2.size(); i++ )

{

cout << v2[i] << " ";

}

cout << endl;

/**//* cout << "Before, v2 is: ";

for( vector<int>::iterator iter =v2.begin() ; iter < v2.end(); iter++ ) {

cout << *iter << " ";

}

cout << endl;//迭代器，相當于指針的概念。。*/

// v2.insert( v2.end(), v1.begin(), v1.end() );//在v2末尾插入v1

// v2.insert(v2.end(),3,'3'); //在v2末尾插入3個51

// swap(v1,v2);

// v1.swap(v2); //交換

// printf("%d\n",v2.at(2)); // 輸出指定位置值

// sort(v2.begin(),v2.end(),cmp); //排序，一直沒弄明白cmp

// sort(v2.begin(),v2.end(),greater<int>()); //遞減排序

// sort(v2.begin(),v2.end(),less<int>()); //遞增排序

// v2.assign(v1.begin(),v1.end());//拷貝v1到v2

// v2.erase(v2.end()-1,v2.end()); //刪除容器元素，不包括第一個數

// v2.clear(); //清空

// v2.resize(2); //修改元素個數

cout << "After, v2 is: ";

for( vector<int>::size_type j = 0; j < v2.size(); j++ )

{

cout << v2[j] << " ";

}

return 0;

}

posted @ 2010-09-03 13:52 jince 閱讀(200) | 評論 (0) | 編輯收藏

C++ 重載流的提取操作

      書上有一個用C++設計自己的輸出/輸入操作，涉及到運算符重載和流提取符重載，挺不錯的！
      代碼如下：
      COMPLEX.HPP文件

#include<iostream.h>

class COMPLEX {

public :

COMPLEX(double r=0,double i=0);

COMPLEX(const COMPLEX& other);

COMPLEX operator +(const COMPLEX& other);

COMPLEX operator -(const COMPLEX& other);

COMPLEX operator -();

COMPLEX operator =(const COMPLEX &other);

friend ostream& operator <<(ostream& stream,COMPLEX& obj);

friend istream& operator <<(istream& stream,COMPLEX& obj);

public :

double real,image;

};

COMPLEX.CPP文件

//COMPLEX.CPP文件

#include "COMPLEX.HPP" //將頭文件包括進去,不能寫成include<COMPLEX.CPP>。。。

COMPLEX::COMPLEX(double r,double i)

{

real=r;

image=i;

return ;

}

COMPLEX::COMPLEX(const COMPLEX& other)

{

real=other.real;

image=other.image;

return ;

}

COMPLEX COMPLEX::operator +(const COMPLEX& other) //運算符+重載參數為COMPLEX類型，返回值為COMPLEX類型的引用，下同

{

COMPLEX temp;

temp.real=real+other.real;

temp.image=image+other.image;

return temp;

}

COMPLEX COMPLEX::operator -(const COMPLEX& other)

{

COMPLEX temp;

temp.real=real-other.real;

temp.image=image-other.image;

return temp;

}

COMPLEX COMPLEX::operator =(const COMPLEX& other)

{

real=other.real;

image=other.image;

return *this;

}

ostream& operator<<(ostream& stream,COMPLEX& obj) //流提取符重載有兩個參數，第一個參數出現在<<操作符左側，為ostream引用，第二個出現在操作符<<右側，為COMPLEX引用，返回值是一個ostream的對象引用，下同

{

stream<<obj.real;

if(obj.image>0) stream<<"+"<<obj.image<<"i";

else if(obj.image<0) stream<<obj.image<<"i";

return stream;

}

istream& operator>>(istream& stream,COMPLEX& obj)

{

cout<<"Input real part:";

stream>>obj.real;

cout<<"input image part:";

stream>>obj.image;

return stream;

}

int main()

{

COMPLEX c1,c2;

cout<<"Input the first complex number c1:"<<endl;

cin>>c1;

cout<<"Input the second compex number c2:"<<endl;

cin>>c2;

cout<<"c1 is"<<c1<<endl;

cout<<"c2 is"<<c2<<endl;

cout<<"c1+c2 is "<<c2+c1<<endl;

cout<<"c1-c2 is "<<c1-c2<<endl;

//操作符原功能任存在

int a=50,b=10;

cout<<"A="<<a<<"\tB"<<b<<endl;

cout<<"A+B is "<<a+b<<endl;

cout<<"A-B is "<<a-b<<endl;

a=-b;

cout<<"A=-B,A="<<a<<"\tB"<<b<<endl;

a=b;

cout<<"A=B,A="<<a<<"\tB"<<b<<endl;

return 0;

}

輸出結果：

posted @ 2010-09-02 22:08 jince 閱讀(501) | 評論 (0) | 編輯收藏

棋盤覆蓋

         網上搜了下棋盤覆蓋，結果看到了哈佛校訓。。。。
         棋盤覆蓋是在一個2^k*2^k的棋盤中存在一個特殊格子，現要求用L型覆蓋整個棋盤（除特殊格子），問如何覆蓋這個棋盤？
         在學校的時候，這題目是只看懂了解題思路，代碼沒仔細看過，現在在重新看的時候，感覺其實也不是那么難看懂！

          先看解題思路截圖：

看到這個截圖你會有何感想呢？其實不就是個分治嘛！將一個2^k*2^k棋盤分割成4個2^(k-1)*2^(k-1),然后問題回到原點，在2^(k-1)*2^(k-1)棋盤中有一個特殊格子，求其用L型骨牌覆蓋方法！

代碼如下：

#include<stdio.h>

int Board[64][64];

int tile;

void ChessBoard(int tr,int tc,int dr,int dc,int size)//tr為棋盤左上角方格行號，tc為棋盤左上角列號，dr為特殊格行號，dc為特殊格列號，size=2^k，棋盤規格

{

if(size==1) //當分到只剩下一個格子的時候,該格就是本次遞歸特殊格

return ;

int t=++tile;

int s=size/2;

if(dr<tr+s&&dc<tc+s) //特殊格在棋盤左上角

ChessBoard(tr,tc,dr,dc,s);

else

{

Board[tr+s-1][tc+s-1]=t;

ChessBoard(tr,tc,tr+s-1,tc+s-1,s);

}

if(dr<tr+s&&dc>=tc+s) //特殊格在棋盤右上角

ChessBoard(tr,tc+s,dr,dc,s);

else

{

Board[tr+s-1][tc+s]=t;

ChessBoard(tr,tc+s,tc+s-1,tc+s,s);

}

if(dr>=tr+s&&dc<tc+s) //特殊格在棋盤左下角

ChessBoard(tr+s,tc,dr,dc,s);

else

{

Board[tr+s][tc+s-1]=t;

ChessBoard(tr+s,tc,tr+s,tc+s-1,s);

}

if(dr>=tr+s&&dc>=tc+s) //特殊格在棋盤右下角

ChessBoard(tr+s,tc+s,dr,dc,s);

else

{

Board[tr+s][tc+s]=t;

ChessBoard(tr+s,tc+s,tr+s,tc+s,s);

}

int main()

{

int i,j,k,l;

/*for(k=0;k<64;k++)

for(l=0;l<64;l++)

{ */

Board[2][1]=0;

tile=0;

ChessBoard(0,0,2,1,4);

for(i=0;i<4;i++)

{

for(j=0;j<4;j++)

{

printf("%d ",Board[i][j]);

}

printf("\n");

}

printf("\n");

// }

return 0;

}

輸出結果：

哈佛校訓：此刻打盹，你將做夢，此刻學習，你將圓夢！受教！！

posted @ 2010-09-02 13:59 jince 閱讀(432) | 評論 (0) | 編輯收藏

快速排序

          公司不發工資了。。。。
         快速排序算法是基于分治算法的一種排序。主要思想分成兩步（從小到大排序）：

         （1）分解，取出排序數列中一個數字，將數分成三段，左邊段數列數值大于等于取出數，右邊段數列值小于等于取出數，中間是取出數；

         （2）遞歸求解；

         第一步其實是根據分治算法的基本思想，將一個規模為n的問題分成3個規模較小的問題，其中規模為1的在這次運算后，就是最后結果中的位置了；

         第二步其實是將規模較小的另兩個數列，繼續分解下去，其中每一次分解都會確定一個數在最后結果中的位置，

         在這樣的思想下，該程序設計最關鍵的一種操作就是怎樣把數組分解成左邊段數列數值大于等于取出數，右邊段數列值小于等于取出數；

         書上的代碼如下：

#include<iostream>

#include<algorithm>

using namespace std;

template <class Type>

void QuickSort(Type a[],int p,int r)

{

if(p<r)

{

int q=Partition(a,p,r); //分解

QuickSort(a,p,q-1); //左半段排序

QuickSort(a,q+1,r); //有半段排序

}

void Swap(int &a,int &b) //交換

{

int c;

c=a;

a=b;

b=c;

}

int Partition(int a[],int p,int r) //分解

{

int i=p,j=r+1; //為啥i=p,j=r+1呢？

int x=a[p]; //因為取第一個數為參考值

while(1) //死循環

{

while(a[++i]<x&&i<r); //一個從左邊找比x大的數

while(a[--j]>x); //一個從右邊找比x小的數

if(i>=j) //死循環跳出條件，為什么是i>=j呢？i>=j意味著j左邊數列值都小于x（包括j），右邊數列值都大于x了！

break;

Swap(a[i],a[j]); //沒跳出死循環，就應該交換

}

a[p]=a[j];

a[j]=x; //交換p與j位置上的值，因為a[j]<=x！！到這里p位置上的數，位置就確定下來了！

return j; //返回位置值，為另兩端提供參數！

}

int main()

{

int i;

int a[10]={3,4,5,3,2,5,6,8,9,2};

for(i=0;i<10;i++)

printf("%d ",a[i]);

printf("\n");

QuickSort(a,0,9);

for(i=0;i<10;i++)

printf("%d ",a[i]);

printf("\n");

return 0;

}

輸出結果：

特殊情況下：如果選取的a[p]是數列最小值，Partition(a,p,r)返回p，a[p]值不變！我測試了一下，是期望結果。。。

網上還有快速排序視屏，巨好玩！
http://v.youku.com/v_show/id_XMTg1MjIwMDY0.html

posted @ 2010-09-01 16:14 jince 閱讀(391) | 評論 (1) | 編輯收藏

整數劃分

        以前做過這么一個題目，在我們學校ACM網上，找了很久沒找到，郁悶！網上走了一遭，基本和書上介紹的差不多，雖然做過但是重新去看思路的時候還是比較慢！！！我再寫一下，加深影響！
         整數劃分就是將一個正整數表示成一系列正整數之和，問有多少種不同劃分方案！
         例如整數6可以劃分成一下11中方案：
        6
        5 + 1
       4 + 2, 4 + 1 + 1
        3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
        2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
        1 + 1 + 1 + 1 + 1 + 1
       如果你是編程好手看到這樣的排列，可能一下子就能想到一種解題思路了！感慨，算法就是在培養解決問題的思路！！言歸正傳！先介紹下書上的思路：
                     一、p(n,m)含義：在正整數n的所有不同劃分中，最大加數不大于m的劃分數（m<=n；m,n>=1）！求整數6有幾種劃分時，既求p(6,6)。。。
                     二、函數遞歸關系：
                            1、n<1||m<1，return 0；
                            2、n==1||m==1，p(n,m)=1；
                            3、n<m，p(n,m)=p(n,n)；例如：p(6,10)=p(6,6)
                            4、n>m，p(n,m)=p(n,m-1)+p(n-m,m)；例如：p(6,5)=p(6,4)+p(2,4)； p(6,2)=p(6,1)+p(4,2)；（這個等式是關鍵）
代碼如下

#include<cstdio>

int q(int n,int m)

{

if((n<1)||(m<1)) return 0;

if(n==1||m==1) return 1;

if(n<m) return q(n,n);

if(n==m) return q(n,m-1)+1;

return q(n,m-1)+q(n-m,m);

}

int main()

{

printf("%d\n", q(6,6));

return 0;

}

寫完書上的解題思路，我突然發現前面我想到的一種解題思路錯了！！不過這種遞歸算法運行效率低，計算整數35分解方案數的時候，計算速度很慢（大概兩秒出現答案14930352），40的時候更慢了- -，我想用二維數組填表的方式應該會快一點！！有更好算法的可以留言！！隨時候教~~

posted @ 2010-08-31 15:25 jince 閱讀(2451) | 評論 (2) | 編輯收藏

僅列出標題

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

牛人

搜索

最新評論

閱讀排行榜

評論排行榜