《剑指offer》--017--打印1到最大的n位数

Myth丶恋晨 2022-05-31 00:36 130阅读 0赞

[《剑指offer》–目录索引][offer]

**题目：**

> 输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。

**思路：**

> ①字符串累加  
> 详细见代码：

int StringAdd(char* number,int n)//字符串累加（代替数字累加）
    {
        int i=n-1;//数组最后一个位置作为个位数开始累加
        for(;i>=0;i--)
        {
            int num=number[i]-'0';//获取当前位置的数
            if(num+1 <= 9)//即表示当前位加1后不需要进位
            {
                number[i]++;//则当前位加1
                return 0;//一次累加结束，返回0
            }
            else//需要进位
            {
                if(i == 0)//如果已经走到数组第一个位置，却还需要进位
                {
                    return 1;//则整个累加结束，返回1
                }
                number[i]='0';//将当前为置0
            }
        }
    }
    
    void PrintString(char* number)//打印累加后的字符串
    {
        char* ret=number;//用于寻找数组中从左往右第一个不为‘0’的位置
        while((*ret) == '0')
        {
            ret++;
        }
        printf("%s ",ret);
    }
    
    void PrintI(int n)//打印1到最大的n位数
    {
        if(n <= 0)
        {
            printf("输入有误！\n");
            return;
        }
        char* number=(char *)malloc(n+1);
        int i=0;
        for(;i < n;i++)
        {
            number[i]='0';
        }
        number[n]='\0';
    
        while(StringAdd(number,n) != 1)
        {
            PrintString(number);
        }
        printf("\n");
    
        free(number);
        number=NULL;
    }

> ②全排列递归法  
> 详细见代码：

void PrintR(char* number,int n,int index)//递归核心代码
    {   
        if(index == n-1)
        {
            PrintString(number);
            return;
        }
        int i=0;
        for(;i<10;i++)
        {
            number[index+1]=i+'0';
            PrintR(number,n,index+1);
        }
    }
    
    void PrintII(int n)
    {
        if(n <= 0)
        {
            printf("输入有误！\n");
            return;
        }
        char* number=(char *)malloc(n+1);
        int i=0;
        for(;i < n;i++)
        {
            number[i]='0';
        }
        number[n]='\0';
    
        int j=0;
        for(;j<10;j++)
        {
            number[0]=j+'0';
            PrintR(number,n,0);
        }
        printf("\n");
        free(number);
        number==NULL;
    }

**测试代码：**

void test1()//测试代码1，字符串累加法
    {
        PrintI(0);
        PrintI(1);
        PrintI(2);
        PrintI(-1);
    }
    
    void test2()//测试代码2，全排列递归法
    {
        PrintII(0);
        PrintII(1);
        PrintII(2);
        PrintII(-1);
    }
    
    int main()
    {
        test1();
        test2();
        return 0;
    }

**运行结果：**  
![这里写图片描述][SouthEast]

[offer]: http://blog.csdn.net/w_y_x_y/article/details/79209805
[SouthEast]: /images/20220531/1dc18588d1f04244aec86ace91f9362d.png