`
YuHuang.Neil
  • 浏览: 187733 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

将一个整数拆分成两个整数的平方和算法

阅读更多
问题:请使用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.


分享到:
评论

相关推荐

    整数开平方算法

    整数开平方算法是数字信号处理中经常需要用到的一种算法。特别是在定点数字信号处理器(DSP)上,由于整数开平方运算通常较为复杂且运算速度要求较高,因此整数开平方算法的性能直接影响整个系统的效率。传统的开...

    桂电计算机组成原理课设,输入包含5个整数(有符号数)的数组M,输出所有负数的平方和

    这个系统的核心任务是处理一个包含五个有符号整数的数组M,并计算其中所有负数的平方和。这是一个典型的数字逻辑与计算机体系结构的应用问题,涉及到硬件描述语言(如VHDL)编程、硬件仿真以及数字信号处理的基本...

    大整数运算库 大整数四则运算,加减乘除开平方

    大整数运算的核心是算法设计,它涉及到一系列高效的数据表示和计算方法。通常,大整数会被表示为数组或链表形式,每个元素存储一个位或一组位。例如,一个大整数可以被拆分成多个32位或64位的整数,这样的设计使得...

    一个整数,它加上100后是一个完全平方数,再加上168又是一个完全平方数,请问该数是多少?

    这个程序使用循环来遍历所有可能的整数,然后判断每个数是否满足条件,即加上 100 后是一个完全平方数,再加上 168 又是一个完全平方数。 这三个问题都可以使用不同的算法和数据结构来解决,例如排列组合、条件语句...

    x是0-31间的整数,用遗传算法求f(x)=x平方的最大值.zip

    “crossover.m”是交叉操作,模拟生物繁殖过程,将两个父代个体的部分基因组合形成新的子代。常见的交叉策略有单点交叉、多点交叉等。 “mutation.m”是变异操作,随机改变个体的部分基因,引入新的遗传信息,防止...

    平方乘算法,密码学中用的

    平方乘算法的基本思想是通过将指数分解为二进制表示,然后逐步进行平方和乘法操作,以减少计算步骤。例如,如果我们要计算 \(a^n \mod m\),可以先将 \(n\) 转换为二进制形式 \(n = 2^k + 2^{k-1} + ... + 2^1 + 2^0...

    信息安全中模重复平方算法和欧几里得算法

    在信息安全领域,模重复平方算法(Modular Exponentiation,也称为快速幂运算)和欧几里得算法(Euclidean Algorithm)是两个重要的数学工具,它们在加密算法、数字签名和密钥交换等方面发挥着关键作用。下面将详细...

    模重复平方算法

    模重复平方算法( Modular Exponentiation,也称为快速幂运算)是计算机科学中,特别是密码学和数论领域中常用的一种高效计算大整数幂的方法。这个算法在处理模意义下的幂运算时非常有效,特别是在涉及到大整数时,...

    c++简单习题求两个整数的最大公约数和最小公倍

    算法基于原理:两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。代码中用do-while循环实现,直到余数为0,此时的除数即为GCD,乘以两数之积得到最小公倍数LCM。 2. 位操作: 输入一个整数,将它...

    Minimal m Sums 给定n 个整数组成的序列,现在要求将序列分割为m 段,每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小?

    - 第一行包含两个整数 n 和 m,分别表示序列的长度和分割的段数。 - 第二行包含 n 个整数,表示序列中的元素。 **输出**: - 输出一行,包含一个整数,即 m 个子序列的和的最大值的最小可能值。 #### 示例 **输入...

    算法-数论- 整数分解.rar

    这个主题通常涉及到将一个大整数表示为两个或多个较小整数的乘积,比如找到两个质数p和q使得n=p*q。这种分解过程在诸如RSA公钥加密算法中起着至关重要的作用。 在数论中,整数分解问题的难度是众所周知的。对于...

    平方乘算法_平方乘算法_zip_

    平方乘算法,也被称为“快速幂运算”或“Exponentiation by Squaring”,是一种在计算大整数的幂时非常有效的算法。它基于这样一个简单的思想:任何正整数的幂都可以通过连续乘以自身来得到,而每次乘以自身可以避免...

    对大整数n = pq 分解的一个有效的搜索算法

    - **大整数分解**: 指的是将一个大整数分解为其素因数的过程。 - **RSA算法**: 基于大整数分解难题的一种非对称加密算法。 - **弱密钥**: 在某些条件下容易被破解的密钥。 #### 调差思想与搜索算法 - **调差思想**...

    算法-求正整数2和n之间的完全数(信息学奥赛一本通-T1150).rar

    在这个题目“算法-求正整数2和n之间的完全数(信息学奥赛一本通-T1150)”中,任务是编写一个程序或算法,找出给定正整数n范围内的所有完全数。首先,我们需要理解如何判断一个数是否为完全数。以下是解决这个问题的...

    java求一个整数的因子.7z

    在最坏的情况下,如果`num`是一个完全平方数,因子的数量会是其平方根的两倍,因此空间复杂度是O(√n)。 在实际应用中,可能需要对这段代码进行优化,特别是在处理大整数时。例如,我们可以通过只遍历到√n来减少...

    128位大整数运算源代码

    大整数的乘幂运算则可能用到快速幂算法,它通过不断平方和乘法操作,大大减少了运算次数。 此外,二进制和十进制转换也是大整数处理的一部分。从10进制转2进制,可以使用除2取余法;反之,从2进制转10进制,则通常...

    求子集问题--一个ACM程序竞赛题

    该问题的描述是:已知N个大于0的整数构成一个集合,即{1,2,3,……,N},求其所有的非空且元素不相邻的子集,计算所有子集的乘积的平方的和。 知识点1:子集的概念 子集是集合中的一部分元素的集合。在这个问题中...

    大整数问题

    在计算机科学中,大整数(Big Integer)是指超过...然而,实际的高性能大整数库,如Java的`BigInteger`或C++的GMP(GNU Multiple Precision Arithmetic Library),通常会使用更高效的数据结构和算法来优化这些操作。

    大整数C++ 类 源代码

    它会处理两个大整数对象的乘法操作,生成一个新的大整数结果。 2. `bigintini.cpp`:这个文件可能负责大整数类的初始化。初始化可能包括从字符串、普通整型数值或随机生成的大整数创建大整数对象。此外,可能还包括...

Global site tag (gtag.js) - Google Analytics