由一道面试题（打印从1到最大的n位数）的思考,该如何处理

由一道面试题（打印从1到最大的n位数）的思考
如果在百度中搜索下这个面试题，基本上都是这个的”拷贝“（当然我不是说这个是原创，其他的是拷贝的哈），链接为：http://blog.csdn.net/zhaojinjia/article/details/8776639
我在看代码时候，第一个函数，我就感觉很是莫名其妙，请看下面的代码段：

char CharPlus(char a)  
{  
    char b;  
    switch ( a )  
    {  
    case '0': b = '1';  break;  
    case '1': b = '2';  break;  
    case '2': b = '3';  break;  
    case '3': b = '4';  break;  
    case '4': b = '5';  break;  
    case '5': b = '6';  break;  
    case '6': b = '7';  break;  
    case '7': b = '8';  break;  
    case '8': b = '9';  break;  
    case '9': b = '0';  break;  
    default:  cout<<"error"<<endl;  
    }  
    return b;  
}  

仔细看下就知道他其实想表达的意思就是字符加一，可是用这个方法去加，我个人来看是呵呵的，字符在c语言里面是可以与整数互用的，直接字符加一不就行了？第一种方法，大家很容易看懂，可是第二种方法我是看了很久也没弄明白，递归，递归，出口很是不好理解！
在我想来一个数不管他是字符串还是系统的类型（int，long int等），他的加法不就是和我们刚上学时的一样吗！个位加一，如果有进位十位加一，就是这个过程啊！怎么还要用递归。
下面是我的实现：
我实现了一个蹩脚的大整数类（之所以说蹩脚是因为这个整数的大小还要受外界的影响，按道理来说应该是无穷的）。

#include<iostream>
#include<vector>

class MaxOfnDigits
{
private:
std::vector<char> str;//数字字符串
bool Inc_char(char& ch);//自加字符ch
public:
explicit MaxOfnDigits(const std::vector<char>& s):str(s){}
~MaxOfnDigits(){}
MaxOfnDigits& operator++();
/*加一函数，注意这里的++与平常的++有点不同，如果这样用的话（x++），
它会先进入函数进行加一，而后取得表达式的值，也就是说表达式x++的值
是加一后的值，其实通过修改这个函数可是实现后缀这个性质，
可是我后来调试的时候,发现这个情况的，也就没大改了。*/
friend std::ostream& operator<<(std::ostream& out,const MaxOfnDigits& tem);//输出函数
bool Is_over()const;//通过判断是否所有的为都是9来判断是否越界
};
MaxOfnDigits& MaxOfnDigits::operator ++()
{
unsigned int n=this->str.size()-1;//n初始化为个位
while(Inc_char(this->str[n]))//有进位
{
if(!(--n) && this->str[0]=='9')
{
std::cout<<"ove of \n"<<std::endl;
break;
}
}
return *this;
}

bool MaxOfnDigits::Inc_char(char& ch)
{
if(!(ch>47 && ch<58))
std::cout<<"no number\n"<<std::endl;
if(ch!='9')//have no over bit
{
ch=ch+1;
return false;
}
else
{
ch='0';
return true;
}
}

std::ostream& operator<<(std::ostream& out,const MaxOfnDigits& tem)
{
bool first=true;
for(int i=0;i<tem.str.size();i++)
{
if(!(tem.str[i]-'0') && first)
{
continue;
}
out<<tem.str[i];
first=false;
}

return out;
}

bool MaxOfnDigits::Is_over()const
{
for(int i=0;i<this->str.size();i++)
{
if('9'!=this->str[i])
{
return false;
}
}
return true;
}

驱动代码：

int main()
{
int count=3;
std::vector<char>  vec(count,'0');//
MaxOfnDigits maxofn(vec);

int i=1;
while(1)
{
std::cout<<maxofn++<<"";
if(maxofn.Is_over())
break;
if(!((i++)%10))
std::cout<<std::endl;
}
return 0;
}

以上代码均在VC6.0中调试的。可以看出这个类的可以添加很多功能，比如大整数相加，减，乘除等。
[解决办法]
keputie
[解决办法]
用递归的话打印1~99999就会出现溢出了吧，可以很方便的使用两重循环实现呀：

#include <stdio.h>
#define MAX 100

void printFrom1ToMaxNDigisNum(int n)
{
    int i;
    if(n < 10){
        int limit = 1;
        for(i = 0; i < n; ++i) limit *= 10;
        for(i = 1; i < limit; ++i) printf("%d\n", i);
    }
    else{
        char num[MAX+1];
        int head = n-1, tail = n-1; 
 

        num[n] = '\0';
        num[tail] = '1';
        while(1){
            puts(num+head);
            //increase number
            for(i = tail; i >= head; --i){
                if(num[i] < '9'){
                    ++num[i];
                    break;
                }
                else num[i] = '0';
            }
            //increase digits
            if(i < head){
                if(--head < 0) break;
                num[head] = '1';
            }
        }
    }
    //puts("Done!");
}

int main()
{
    freopen("E:\\out.txt", "w", stdout);

    int n;
    scanf("%d", &n);
    printFrom1ToMaxNDigisNum(n);

    return 0;
}

[解决办法]
“字符在c语言里面是可以与整数互用的” 
[解决办法]
撇开面试本身不谈，就实现而言，在下有如下疑问：
1、std::string 是不是比 std::vector<char> 更适合解决这个问题？
2、这个友元<<，是不是在内类实现就行了，共一行代码。
3、用的着is over 吗？ 解决不了9999的问题？
[解决办法]

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

class Number
{
public:
Number & operator ++()
{
size_t i = 0;

for (; i < m_value.size(); ++i)
{
if (m_value[i] == '9')
{
m_value[i] = '0';
}
else
{
++m_value[i]; 
break;
}
}

if (i == m_value.size())
{
m_value.push_back('1');
}

return *this;
}

size_t size() const 
{
return m_value.size();
}

template <typename OutputStream>
friend OutputStream & operator << (OutputStream & stream, const Number & n)
{
std::copy(n.m_value.rbegin(), n.m_value.rend(), std::ostream_iterator<char>(stream));
return stream;
}

private:
std::vector<char> m_value;
};

int main(int argc, char * argv[])
{
unsigned int n = 3; //最大的N位数 

Number num;

while((++num).size() <= n)
{
std::cout << num << '\n';
}

return 0;
}

[解决办法]
俺也来一发，凑个热闹。
类：

#pragma once

#include <string>

class CInteger
{
public:
CInteger(void) { _number = "0"; _carry = '0'; }
CInteger(std::string& integer) { _number = integer; _carry = '0'; }
CInteger(const char * integer) { _number = integer; _carry = '0'; }
virtual ~CInteger(void){}

private:
std::string_number;
char_carry;
inline chardecimal_add(char _left, char _right)
{
char _result = _left + _right - '0';
if(_result > '9')
{
_result -= 10;
_carry += 1;
}
return _result;
}

public:
voiddecimal_add()
{
std::string::reverse_iterator itr_number = _number.rbegin();
*itr_number = decimal_add(*itr_number, '1');
while(_carry != '0')
{
char tmp_carry = _carry;
_carry = '0';
itr_number++;
if(_number.rend() == itr_number)
{
_number.insert(_number.begin(), '0');
itr_number = _number.rend() - 1;
}
*itr_number = decimal_add(*itr_number, tmp_carry); 
 
}
}
inline unsigned int length(){ return _number.size(); }
inline std::stringnumber(){ return _number; }
};

测试代码：

// Testor.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "Integer.h"
#include <iostream>

int _tmain(int argc, _TCHAR* argv[])
{
CInteger integer("1");
unsigned int n = 0;
std::cout << "n =";
std::cin >> n ;
for(int i = 0; integer.length() <= n; i++)
{
std::cout << integer.number() << std::endl;
integer.decimal_add();
}
return 0;
}

查看更多 下一篇