试题 算法训练 YBH数数(C语言版)

问题描述

　　YBH数学很差，她数数时分不清4,5和8；我们定义YBH[i]为YBH的计数法对应的i的值。

　　规定：YBH[4] = 5,YBH[5] = 8；YBH[i]运算规则如下：

　　① YBH[i+j] = YBH[i] + YBH[j]

　　② YBH[i*j] = YBH[i] * YBH[j]

　　我们会发现，用不同方法算出的YBH[i]的值是不同的，例如：当i=20时，

　　YBH[20] = 5*YBH[4] = 25；

　　YBH[20] = 4*YBH[5] = 32；

　　YBH[20] = YBH[4] * YBH[5] = 40；

　　......

　　我们规定：F[i]为YBH[i]的最大值，现在请你编写一个程序，输入一个数n，输出F[n]的值，若F[n]没有意义，输出-1。

输入格式

　　一个数n(8 <= n <= 1000)

输出格式

　　输出F[n]的值.

样例输入

20

样例输出

40

样例输入

11

样例输出

-1

老规矩话不多说上代码（蓝桥网站测试未通过，但是自己机器上能用的三个例子都对。自己也计算了几个数也对，如果各位大佬发现问题烦请告知。）

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n,i=0,j=0;
    scanf("%d",&n);
    int ybh[1001];
    if (n>=8 && n<=1000)
    {
        for (i=0; i<n+1; i++)
        {
            if(i<16)
            {
                if(i<8)
                {
                    if(i==4 || i==5)
                    {
                        ybh[4]=5;
                        ybh[5]=8;
                    }
                    else
                    {
                        ybh[i]=-1;
                    }
                }
                if(i>=8)
                {
                    if(i%4==1 || i%5==4 || i%4==0 || i%5==0)
                    {
                        if(ybh[i-4]+5>=ybh[i-5]+8)
                        {
                            ybh[i]=ybh[i-4]+5;
                        }
                        else
                        {
                            ybh[i]=ybh[i-5]+8;
                        }
                    }
                    else
                    {
                        ybh[i]=-1;
                    }
                }

            }
            if(i>=16)//乘法关系，加法关系
            {
                int jia=0,cheng=0;
                for (j=4; j<=(i-4)/2; j++)
                {
                    if(ybh[j]==-1 || ybh[i-j]==-1)
                    {
                        continue;
                    }
                    else
                    {
                        if(jia>=ybh[i-j]+ybh[j])
                        {
                            jia=jia;
                        }
                        else
                        {
                            jia=ybh[i-j]+ybh[j];
                        }
                    }
                }
                for(j=4; j<=i/4; j++)
                {
                    if(ybh[j]!=-1 && (i*1.0)/j==i/j)
                    {
                        if(cheng>=ybh[j]*ybh[i/j])
                        {
                            cheng=cheng;
                        }
                        else
                        {
                            cheng=ybh[j]*ybh[i/j];
                        }
                    }
                }
                if(jia>=cheng)
                {
                    ybh[i]=jia;
                }
                if(cheng>=jia)
                {
                    ybh[i]=cheng;
                }
            }
        }

    }
    else
    {
        printf("%d",-1);
    }
    printf("%d",ybh[n]);
    return 0;
}
           

很明显这还是一道动态规划，经过这几天的折磨，终于啃下三道题，慢慢对动态规划有了一定的理解，话不多说回到问题上来。

分析问题，问题的大意是让我们输入一个数，计算YBH计算规则下的对应的数，而YBH很明显已经给出了是一个一维数组，这问题的数组不就来了吗？很明显ybh[i]就代表i这个数再YBH计算规则下对应的数，那么到这里动态规划的第一步就解决了。

接下来是第二步，状态转移，说白了就是元素计算关系，这里题目已经给出了，有两种计算关系一种是加法，一种是乘法，在这里我特意说明一下，这里的加法和乘法不是必须用4 和5 来计算，我就在这块纠结了很久，比如20，可以是ybh[4]+ybh[16]，也可以是ybh[5]+ybh[15]。

那么接下来就是设计程序了，但是还有一个特殊的规则就是没有意义的n值为-1，

那么这里我们就需要思考了，什么样的n是无意义的，很明显从4开始6和7很明显是没有意义的因为不管4和5怎么组合都是组合不成6和7的，那么有什么特征呢?

额！其实特征就是4 和5组不成这个数，是不是感觉我再说废话，巧了我也是这么觉得的。

有了这么一个限制是不是觉得很头痛，但是是不是后面的所有数中还存在组不成的数呢？

仔细看4 和5我们发现这两个数只相差1而且还是一个奇数和一个偶数，而奇数和偶数是可以组成任意奇数和偶数的，当然这里我们有6和7并不能被4和5组成，很明显就存在一个数为界限，这个数以后的所有数都可以由4和5组成，这个数之前的数含有不能组成的数，那么充当这个界限的数是谁呢？有什么特征呢？

来开动脑筋，仔细想想是不是只要有连续的四个数都有意义后面的数一定是都有意义的，因为又形成了一个循环，多了一个整的四对不对，其实有个笨办法就是一个数一个数的算，但是我比较懒，一琢磨他给的例子是20，4*4=16而刚好16到20四个数都有意义，我就用16做了这个界限，当然16之前的15 14 13 12 都可以由4 和5 组成，但是我比较懒就没多想，

那么到这里题目我们已经思考的差不多了，剩下的就是设计程序了，很明显这个界限之前的数字我们需要特殊处理，这个特殊处理就是需要我们进行-1处理，让没有意义的数的ybh[i]=-1，后续的数我们只需要按照加法和乘法的规则进行取最大值就行了，当然程序中的取大值操作略显繁琐，我知道可以利用函数调用，但是蓝桥测试没通过我就改成这样了，当然还是没通过，而我选取的这个16这个数字比较特殊，这个数之前的数字，用加法和乘法计算的结果都是一样的，原因是计算的规则和乘法计算的规则造成的，但是我仔细一想这个数的特异性在于这个数之前的所有数用乘法规则是不成立的，因为16=4*4 我们的计算规则要求从4开始计算，所以乘法生效的时候这个数是16。

到这里这道题的思路就讲完了。