数组全排列和最“完美数组”问题

要求一个数组邻近元素之和可开整数平方,试问,该数组有多少种组合,推荐使用开方函数进行校验

先进行组合式排列,先算出所有组合(实际上每一种组合计算出的同时进行验证——一个循环验证操作),验证比较常规,关键是如何求解全排列?

#include <iostream>
using namespace std;
int record = 0;
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}
void perm(int list[], int low, int high)
{
    if (low == high)
    {
        int i;
        for (i = 0; i <= low-1; i++)
        {
            //int tmp = list[i] * list[i] + list[i + 1] * list[i + 1];
            int tmp = list[i] + list[i + 1];
            if (sqrt(double(tmp)) != int(sqrt(double(tmp))))
            {
                break;
            }
            //cout << sqrt(tmp) << " ";
        }
        //cout << endl;
        if (i == low - 1)
        {
            record++;
        }
    }
    else
    {
        for (int i = low; i <= high; i++)
        {
            swap(list[i], list[low]);
            perm(list, low + 1, high);
            swap(list[i], list[low]);
        }
    }
}
int main()
{

    int list[] = { 1, 17, 8 };
    perm(list, 0, 2);
    cout << record << endl;
    return 0;
}

在别人的基础上(了解运行逻辑即可),加点自己的实现想法(确保能够完成目标),以最快的速度解决问题,毕竟,一个人阅历有限,不可能什么都了解(真是滑天下之大稽)

发表评论

电子邮件地址不会被公开。 必填项已用*标注