蓝桥杯之特殊回文串-剪枝法(c++代码实现)

上文链接:蓝桥杯之十六进制与十进制互转简化(c++代码实现)


资源限制

时间限制:1.0s 内存限制:512.0MB

问题描述

  123321是一个非常特殊的数,它从左边读和从右边读是一样的。
输入一个正整数n, 编程求所有这样的五位和六位十进制数,满足各位数字之和等于n 。

输入格式

  输入一行,包含一个正整数n。

输出格式

  按从小到大的顺序输出满足条件的整数,每个整数占一行。

样例输入

52

样例输出

899998
989989
998899

数据规模和约定

  1<=n<=54。

算法展示

#include <iostream>
using namespace std;

//查找五位数中特殊回文串
void find_five(int sum)
{
    //第一位数 
    for(int i = 1;i<=9;i++)
    {
        if(sum-36<=i)//判断 
        {
            //第二位数 
            for(int j = 0;j<=9;j++)
            {
                //判断 
                if((sum-27)<=(i+j))
                {
                        //第三位数 
                        for(int k = 0;k<=9;k++)
                        {    
                            //判断
                            if((sum-18)<=(i+j+k)) 
                                //第四位数 
                                for(int J = 0;J<=9;J++)
                                {
                                    //判断
                                    if((sum-9)<=(i+j+k+J)&&J==j)
                                    {
                                        //第五位数 
                                        for(int I = 0;I<=9;I++)
                                        {
                                            //判断 
                                            if(sum==(i+j+k+J+I)&&I==i)
                                            {
                                                cout<<i<<j<<k<<J<<I;
                                                cout<<"\n";
                                            }        
                                        }
                                    }
                                         
                                } 
                        } 
                } 
            }    
        }     
    }
}
//查找五位数中特殊回文串
void find_six(int sum)
{
    //第一位数 
    for(int i = 1;i<=9;i++)
    {
        if(sum-45<=i)//判断 
        {
            //第二位数 
            for(int j = 0;j<=9;j++)
            {
                //判断 
                if((sum-36)<=(i+j))
                {
                        //第三位数 
                        for(int k = 0;k<=9;k++)
                        {    
                            //判断
                            if((sum-27)<=(i+j+k)) 
                                //第四位数 
                                for(int K = 0;K<=9;K++)
                                {
                                    //判断
                                    if((sum-18)<=(i+j+k+K)&&k==K)
                                    {
                                        //第五位数 
                                        for(int J = 0;J<=9;J++)
                                        {
                                            if((sum-9)<=(i+j+k+K+J)&&J==j)
                                            //第六位数 
                                                for(int I=0;I<=9;I++)
                                                {
                                                    //判断 
                                                    if(sum==(i+j+k+K+J+I)&&I==i)
                                                    {
                                                        cout<<i<<j<<k<<K<<J<<I;
                                                        cout<<"\n"; 
                                                    }    
                                                } 
                                                    
                                        }
                                    }
                                         
                                } 
                        } 
                } 
            }    
        }     
    }
}

int main()
{
    int sum;
    cin>>sum;
    //特殊回文串和大于45则一定是六位数,反之则有可能是五位数或六位数
    if(sum>45)
    {
        find_six(sum);
    }
    else
    {
        find_five(sum);
        find_six(sum);
    }
    return 0;
}
    

该算法之我的总结

  • 我利用剪枝法(减少实际运行中不可能出现情况)对每层(每位数)的不可能情况进行排除,详细排除情况分析上面代码即可
  • 针对特殊回文数的性质开始时将回文数的和按照是否大于45进行分类,这样做也是剪枝法的体现。

下文链接:蓝桥杯之杨辉三角-难度:易(c++实现)

评论

暂无评论