将一个整数拆分成两个整数的平方和算法_C/C++_编程开发_程序员俱乐部

问题：请使用C/C++写一个程序实现将一个整数拆分成两个整数的平方和，把所有的可能的组合都要计算出来。

答：假定输入的整数为n，则扫描1-(n的平方根)之间的整数，令row=1，column＝(int)(sqrt((double)given)+0.5)，使得row*row+column*column=n的数输出即可。

代码如下所示：

//
//  main.cpp
//  MyProjectForCPP
//
//  Created by labuser on 11/2/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <math.h>

using namespace std;


int main (int argc, const char * argv[])
{
    int given;
    int row,column;
    int count;
    char line[100];
    
    printf("\nRepressenting a Given Number as the the Sum of Two Squares");
    printf("\n==========================================================\n");
    printf("\nAn Integer Please ---> ");
    gets(line);
    
    given = atoi(line);
    printf("\nCount     X       Y");
    printf("\n------  -----  ------");
    
    row =1;
    column=(int)(sqrt((double)given)+0.5);
    while (row<=given && column>0) {
        if(row*row+column*column==given){
            ++count;
            printf("\n%5d%7d%7d",count,row,column);
            ++row;
            --column;
        }
        else if(row*row+column*column>given)
        {
            --column;
        }else{
            ++row;
        }
    }
    
    if(count==0){
        printf("\n\nSorry, NO ANSWER found.");
    }else{
        printf("\n\nThere are %d possible answers.\n",count);
    }
    
    return 0;
}

运行结果：
Repressenting a Given Number as the the Sum of Two Squares
==================================================
An Integer Please ---> 200

Count     X       Y
------  -----  ------
    1      2     14
    2     10     10
    3     14      2

There are 3 possible answers.