1812.完美立方

题目

描述 形如a3= b3 + c3 + d3的等式被称为完美立方等式。例如123= 63 + 83 + 103 。编写一个程序，对任给的正整数N (N≤100)，寻找所有的四元组(a, b, c, d)，使得a3 = b3 + c3 + d3，其中a,b,c,d 大于 1, 小于等于N，且b<=c<=d。

输入 一个正整数N (N≤100)。

输出 每行输出一个完美立方。输出格式为：
Cube = a, Triple = (b,c,d)
其中a,b,c,d所在位置分别用实际求出四元组值代入。

请按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则b值小的优先输出、仍相同则c值小的优先输出、再相同则d值小的先输出。

样例输入

24

样例输出

Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)

分析

1. bcd一定小于a
2. 按照题目要求, 从a开始走循环
3. 去掉重复的

代码

#include<iostream>
using namespace std;


void mySort(int *a){//冒泡排序
    int t;
    if(a[0] > a[1]){
        t = a[0];
        a[0] = a [1];
        a[1] = t;
    }
    if(a[1] > a[2]){
        t = a[1];
        a[1] = a [2];
        a[2] = t;
    }
    if(a[0] > a[1]){
        t = a[0];
        a[0] = a [1];
        a[1] = t;
    }
}

bool compare(int *a, int b[100000][3], int mm){//传入被比较值和数据库,mm作计数器减少性能开支
    for(int i = 0; i < mm; i++){
        if(a[0] == b[i][0] && a[1] == b[i][1] && a[2] == b[i][2]){
            return true;
        }
    }
    return false;
}

int main(){
    int a;
    cin >> a;
    int mem[100000][3] = {0, 0, 0};//记忆数组
    int mm = 0;
    for(int i = 2; i <= a; i ++){
        for(int j = 2; j < i; j++){
            for(int m = 2; m < i; m++){
                for(int n = 2; n < i; n++){
                    if(i * i * i == j * j * j + m * m * m + n * n * n){
                        int c[3] = {j, m, n};
                        mySort(c);//对符合条件的数组排序
                        if(!compare(c, mem, mm)){
                            mem[mm][0] = c[0];
                            mem[mm][1] = c[1];
                            mem[mm][2] = c[2];
                            mm++;
                            cout << "Cube = "<< i << "," << " Triple = (" << j << "," << m << "," << n << ")" << endl;
                        }
                    }
                }
            }
        }
    }
    return 0;
}