首页 技术 正文
技术 2022年11月23日
0 收藏 403 点赞 2,268 浏览 3406 个字

【面试题012】打印1到最大的n位数 

大数问题

字符串中的每一个字符都是‘0’到‘9’之间的某一个字符,用来表示数字中的一位,因为数字最大是n位的,因此我们需要一个长度为n+1的字符串,字符串的最后一个是结束符号‘\0’,当实际数字不够n位的是哦互,在字符串的前半部分补0。

我们要做的是,在字符串上面做模拟加法,然后把字符串表达的数字打印出来。

怎么判断增加的字符串是不是达到我们要求的最大的数字啦,这里很关键,isOverflow做判断,

打印函数,也得定制,因为当数字不够n位的时候,我们在数字的前门补0,

方法一,是模拟加法运算的过程,

方法二,是n位所有的十进制数其实就是n个从0到9的全排列,也就是说,我么把数字的每一个位都从0到9排列一遍,就得到了所有的十进制数,

PrintNum.cpp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
  #include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

void PrintNumber(char *number);
bool Increment(char *number);
void Print1ToMaxOfNDigitsRecursively(char *number, int length, int index);

/*方法一*/
void Print1ToMaxOfNDigits_1(int n)
{
    if(n <= 0)
    {
        return ;
    }
    char *number = new char[n + 1];
    memset(number, ‘0’, n);
    number[n] = ‘\0’;

while(!Increment(number))
    {
        PrintNumber(number);
    }

delete []number;
}

/*
 * 字符串number表示一个数字,在number上增加1
 * 如果做加法溢出,则返回true,否者为false
 */
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;
        if(i == nLength – 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 Print1ToMaxOfNDigits_2(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 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);
    }
}

/*
 * 公共函数
 * 字符串number表示一个数字,数字有若干个0开头
 * 打印出这个数字,并且忽略开头的0
 */
void PrintNumber(char *number)
{
    bool isBeginning0 = true;
    int nLength = strlen(number);

for(int i = 0; i < nLength; ++i)
    {
        if(isBeginning0 && number[i] != ‘0’)
        {
            isBeginning0 = false;
        }
        if(!isBeginning0)
        {
            cout << number[i];
        }
    }
    cout << “\t”;
}

/*测试代码*/
void Test(int n)
{
    printf(“Test for %d begins:\n”, n);

Print1ToMaxOfNDigits_1(n);
    Print1ToMaxOfNDigits_2(n);

printf(“Test for %d ends.\n”, n);
}

int main()
{
    int n = 1;
    Print1ToMaxOfNDigits_1(n);
    Print1ToMaxOfNDigits_2(n);
    return 0;
}

运行结果:

1       2       3       4       5       6       7       8       9           1       2       3       4       5       6       7       8       9 

Makefile:

1
2
3
4
5
6
7
8
9
10
11
12
  .PHONY:clean  
CPP=g++  
CFLAGS=-Wall -g  
BIN=test  
OBJS=PrintNum.o  
LIBS=  
$(BIN):$(OBJS)  
    $(CPP) $(CFLAGS) $^ -o $@ $(LIBS)  
%.o:%.cpp  
    $(CPP) $(CFLAGS) -c $< -o $@  
clean:  
    rm -f *.o $(BIN)  

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141429.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站