输出1到最大的n位数

叁歲伎倆 2022-08-05 10:25 151阅读 0赞

例如：输入3，输出 1 ~ 999，必须考虑大数问题

/* 打印从 1到最大的n位数 */
    bool Increment(char *number)
    {
    	bool isOverflow = false;
    	int nTakeOver = 0;
    	int nLength = strlen(number);
    
    	for (int i = nLength-1; i >= 0; i--)
    	{
    		int nSum = number[i] - '0' + nTakeOver; //初始置为 0
    		if (i == nLength - 1) //第一位保证必须是 1
    			nSum++;
    		if (nSum >= 10) 
    		{
    			if (i == 0)
    				isOverflow = true;
    			else
    			{
    				nSum -= 10;
    				nTakeOver = 1;
    				number[i] = '0' + nSum;
    			}
    		}
    		else
    		{
    			number[i] = '0' + nSum;
    			break;
    		}
    	}
    	return isOverflow;
    }
    
    void PrintNumber(char *number)
    {
    	bool isBeginning0 = true;
    	int nLength = strlen(number);
    
    	for (int i = 0; i < nLength; ++i)
    	{
    		if (isBeginning0 && number[i] != '0') //找到第一位不为0的数字字符
    			isBeginning0 = false;
    		if (!isBeginning0)  //从第一位不为0的数字字符开始打印
    			printf("%c", number[i]);
    	}
    	printf("\t");
    }
    
    void PrintToMaxOfNDigits(int n)
    {
    	if (n <= 0)
    		return;
    	char *number = new char[n+1]; //开辟n+1大小的空间
    	memset(number, '0', n); //前n位置0
    	number[n] = '\0'; //末尾置为'\0'
    
    	while (!Increment(number))
    		PrintNumber(number);
    
    	delete []number;
    
    }
    
    //
    /* 方法二 */
    void Print1ToMaxOfNDigitsREcursively(char *number, int length, int index)
    {
    	if (index == length - 1)
    	{
    		PrintNumber(number);
    		return;
    	}
    	for (int i=0; i<10; ++i)
    	{
    		number[index+1] = i + '0';
    		Print1ToMaxOfNDigitsREcursively(number, length, index+1);
    	}
    }
    
    void Print1ToMaxOfNDigits(int n)
    {
    	if (n<=0)
    		return;
    	char *number = new char[n+1];
    	number[n] = '\0';
    
    	for (int i=0; i<10; ++i)
    	{
    		number[0] = i + '0';
    		Print1ToMaxOfNDigitsREcursively(number, n, 0);
    	}
    	delete []number;
    }
    
    void main()
    {
    	int n = 3;
    //	PrintToMaxOfNDigits(n);
    	Print1ToMaxOfNDigits(n);
    	
    }

节选《剑指offer》