首页 > 代码库 > 极值问题

极值问题

题目:

已知m、n为整数,且满足下列两个条件:
① m、n∈1,2,...,K,(1≤K≤10^9)

② (n^ 2-mn-m^2)^2=1
编一程序,对给定K,求一组满足上述两个条件的m、n,并且使m^2+n^2的值最大。例如,若K=1995,则m=987,n=1597,则m、n满足条件,且可使m^2+n^2的值最大。

输入

输入仅一行,K的值。

输出

输出仅一行,m^2+n^2的值。

样例输入

1995

样例输出

3524578
题目字数不多,但是条件2看起来貌似有点复杂,但实际上,它也是个突破口;

由条件2:(n^ 2-mn-m^2)^2=1

故而:      (m^2 + mn- n^2)^2=1

继续化简:m^2+mn-n^2=(m+n)^2-mn-2n^2 

                                                =(m+n)^2-(m+n)n-n^2
即:          (n^2-mn-m^2)^2=[(m+n)^2-(m+n)n-n^2]^2

我们观察上述最后的等式,我们可以发现

n->m+n (第一个平方)

m->n,n->m+n(中间的因式)

m->n(第二个平方)

这时我们发现这是我们熟悉的斐波那契数列,这样,这一题的突破口很明显了,m、n都是在K(包括K)之内的最大的两个满足斐波那契数列的数;

另外由于1≤K≤10^9可能m、n数字较大,即会发生数字超限,用两个数组进行平方运算以及相加运算;

#include <iostream>

using namespace std;

void Add(int *arrm, int *arrn, int len)  //大整数相加
{
    int *arr = new int[len + 1];
    for(int i = 0; i < len + 1; i++)
        arr[i] = 0;

    for(int i = 0; i < len; i++)
    {
        arr[i] += arrm[i] + arrn[i];
        if(arr[i] >= 10)  //进位
        {
            arr[i + 1] += arr[i] / 10;
            arr[i] %= 10;
        }
    }
    int index = len;
    while(!arr[index])
    {
        index--;
    }
    for(int i = index; i >= 0; i--)
        cout << arr[i];
    cout << endl;
}



void Mul(int *arr, int *arr1, int len1)  //大整数相乘
{
    for(int i = 0; i < len1; i++)
    {
        for(int j = 0; j < len1; j++)
        {
            arr[i + j] += arr1[i] * arr1[j];
            if(arr[i + j] >= 10)  //进位
            {
                arr[i + j + 1] += arr[i + j] / 10;
                arr[i + j] %= 10;
            }
        }
    }
}

void BigData(int m, int n)
{
    int num1 = m;
    int num2 = n;
    int *arr1 = new int[10];
    int *arr2 = new int[10];
    int len1 = 0, len2 = 0;
    while(num1)  //数字数组化
    {
        arr1[len1++] = num1 % 10;
        num1 /= 10;
    }
    while(num2)
    {
        arr2[len2++] = num2 % 10;
        num2 /= 10;
    }
    int len;
    if(len1 > len2)
        len = 2 * len1;

    else
        len = 2 * len2;
    int *arrm = new int[len];
    int *arrn = new int[len];
    for(int i = 0; i < len; i++)
    {
        arrm[i] = 0;
        arrn[i] = 0;
    }
    Mul(arrm, arr1, len1);  //大整数相乘
    Mul(arrn, arr2, len2);
    Add(arrm, arrn, len);  //相加
}

void Fibo(int K)
{
    if(K < 1)
        return;
    if(K == 1)
    {
        cout << 2 << endl;
        return;
    }

    int m = 1, n = 1;
    int p = m + n;
    while(p <= K)  //寻找满足条件的两个Fibonacci数
    {
        m = n;
        n = p;
        p = m + n;
    }

    if(m < 10000 || n < 10000)
        cout << m * m + n * n << endl;
    else
        BigData(m, n);
}

int main()
{
    int K;
    cin >> K;
    Fibo(K);
    return 0;
}


O(∩_∩)O欢迎指教....