输出1到最大n位数之间的所有数

比如

n = 2

那么从1一直输出到99

分析

直接输出，遇到大数时肯定有问题，比如n=100，存储100位的数据类型不存在。

可以利用数组来存储大数，比如n=100,可以开辟个数组 char a[101]

思路一

模拟现实中的技术方式，逢九进一

参考代码

#include <iostream>
#include <cstring>
using namespace std;

bool minuxOne(char *a, int *end_index, int size)
{
    if((*end_index == size - 1 && a[size - 1] == '0') || *end_index < 0 || *end_index >= size)
        return false;
    int tmp = size - 2;
    if(a[size - 1] != '0')
        --a[size -1];
    else
    {
        a[size - 1] = '9';
        while(1)
        {
            if(a[tmp] == '0')
            {
                a[tmp] = '9';
                --tmp;
            }
            else
            {
                --a[tmp];
                break;
            }
        }
        if(a[*end_index] == '0')
            ++*end_index;
    }
    return true;
}

bool printNum(const int size)
{
    if(size < 0)
        return false;
    char *a = new char[size];
    memset(a, '9', size);
    int end_index = 0;
    while(1)
    {
        if(end_index == size - 1 && a[size - 1] == '0')
            break;
        for(int i = 0; i < size; ++i)
        {
            if(end_index > i && a[i] == '0' )
                continue;
            cout << a[i];
        }
        cout << "\t";
        if(!minuxOne(a, &end_index, size))
            break;
    }
    delete []a;
    return true;
}

int main()
{
    int size = 5;
    printNum(size);
}

结果

输出1到最大n位数之间的所有数

思路二

本质可以看作是全排列，只是前边的0别输出

#include <iostream>
using namespace std;

bool print1ToMaxN(const int n);
bool print1ToMaxNRecursion(char *a, int size, int index);
bool printNum(char *a, int size);
int main()
{
    int size = 3;
    print1ToMaxN(size);
}
    
bool print1ToMaxN(const int size)
{
    if(size <= 0)
        return false;
    char *a = new char[size];
    for(int i = 0; i <= 9; ++i)
    {
        a[0] = i + '0';
        print1ToMaxNRecursion(a, size, 1);
    }
    return true;
}

bool print1ToMaxNRecursion(char *a, int size, int index)
{
    if(size <= 0 || index < 0)
        return false;
    if(index == size)
    {
        printNum(a, size);
        return true;
    }
    for(int i = 0; i <= 9; ++i)
    {
        a[index] = i + '0';
        print1ToMaxNRecursion(a, size, index + 1);
    }
}
    
bool printNum(char *a, int size)
{
    if(size <= 0)
        return false;
    bool IsPre0 = true;
    for(int i = 0; i < size; ++i)
    {
        if(IsPre0 && a[i] != '0')
            IsPre0 = false;
        if(!IsPre0)
            cout << a[i];
    }
    cout << "\t";
}

结果

输出1到最大n位数之间的所有数

分析

1. 输出问题：一开始为0不要输出，这需要输出时判断下

2. 递归全排列的本质原理：每一位字符0~0都有可能，在方位本位的时候递归遍历下一位。

本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3604195.html，如需转载请自行联系原作者

输出1到最大n位数之间的所有数

相关推荐