平方三角形数(立方和)
平方三角形数,也称为三角平方数,是一个既是三角形数又是完全平方数的数。
平方三角形数有无限多个可能的值;前几个是:
0, 1, 36, 1225, 41616...
三角形数或三角数是计数按等边三角形排列的物体。第n个三角形数是具有n个点的三角形排列中的点数,等于从1到n的n个自然数之和。从第0个三角形数开始的三角形数序列是:
0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55...
完全平方数或平方数是某个整数与其自身的乘积。完全平方数的序列是:
0, 1, 4, 9, 16, 25, 36, 49...
问题陈述
给定一个数字Sum。如果Sum等于前n个自然数的立方和,则打印n;否则,打印-1。
示例1
输入
36
输出
3
解释 − Sum是前3个自然数的立方和。
1*1*1 + 2*2*2 + 3*3*3 = 36
示例2
输入
22
输出
-1
解释
1*1*1 + 2*2*2 = 9,而 1*1*1 + 2*2*2 + 3*3*3 = 36,因此,不存在立方和等于Sum的自然数。
我们有两种解决这个问题的方法。
方法1
暴力方法是计算整数的立方并存储它们的和。当和等于或小于给定的Sum时,我们将这样做。然后,如果和等于给定的数字,则打印n,否则打印-1。
伪代码
Start temp = 0 i = 0 While temp <= Sum: i = i + 1 add cube of i to temp if temp is equal to Sum then print n else print -1 End
示例
下面是一个C++程序,用于检查给定数字是否等于前n个自然数的立方和。
#include <iostream> using namespace std; // This function returns n if the sum of cubes of first // n natural numbers is equal to the given Sum int calcSquaredTriangularNumber(int Sum){ // initialize a temporary variable to store sum int temp = 0; // Adding cubes of the numbers starting from 1 int n = 0; while ( temp < Sum){ n++; temp += n * n * n; } // If temp becomes equal to sum return n if (temp == Sum){ return n; } // otherwise return -1 return -1; } int main(){ int Sum = 36; // Function call int n = calcSquaredTriangularNumber(Sum); if(n>0){ cout << n ; return n; } else{ cout << "-1"; } return 0; }
输出
对于输入36,上面的C++程序将产生以下输出:
3
方法2
现在我们将研究一个更有效的解决方案。
首先,我们将检查给定数字是否为完全平方数。
如果不是,我们将返回-1。
如果它是完全平方数,那么我们将进一步检查其平方根是否为三角形数。
如果是,则返回根。如果不是,则返回-1。
伪代码
Start check if the Sum is a perfect square find the squareRoot of the Sum checking if the squareRoot is a triangular number if true then return root else return false End
示例
下面是一个C++程序,用于检查给定数字是否等于前n个自然数的立方和。
#include <bits/stdc++.h> using namespace std; // Calculates the root of n(n+1)/2 = numif the root is an integer, returns the root else returns -1 int checkTriangularNum(int num){ if (num < 0){ return false; } // Converting the equation n*(n+1)/2 = num in the form of a(n^2) + bn + c = 0"; int a = 1, b = 1; int c = num * (-2); int dis = (b * b) - (4 * a * c); if (dis < 0) return -1; // calculating the roots float root1 = ( -b + sqrt(dis)) / (2 * a); float root2 = ( -b - sqrt(dis)) / (2 * a); // checking if root1 is an integer if (root1 > 0 && floor(root1) == root1){ return root1; } // checking if root2 is an integer if (root2 > 0 && floor(root2) == root2){ return root2; } return -1; } // Calculates the square root of the numberreturns the root if it an integer, else returns -1 int checkPerfectSquare(double x){ // floating point value of square root double squareRoot = sqrt(x); // checking if the root is integer if ((squareRoot - floor(squareRoot)) == 0) return floor(squareRoot); else return -1; } // This function returns n if the sum of cubes of first // n natural numbers is equal to the given Sum int calcSquaredTriangularNumber(int Sum){ // checking if Sum is a perfect square int squareRoot = checkPerfectSquare(Sum); // if it's not a perfect square return -1 if (squareRoot == -1) return -1; // if is a perfect square, then check if it's a // triangular number or not return checkTriangularNum(squareRoot); } int main(){ int Sum = 36; // Function Call int n = calcSquaredTriangularNumber(Sum); if(n>0){ cout << n ; return n; } else { cout << "-1"; } return 0; }
输出
对于输入36,上面的C++程序将产生以下输出:
3
广告