算法练习-01

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 5 分钟

九月份算法实战总结，方便以后自己温故知新！

Problem-01 小数问题

给定两个正整数A和B，求A/B的最后一位小数的值。如果A/B是无限循环小数或者是整数则输出0。
[输入]

输入有多行，每行两个正整数A和B

[输出]

对于每组输入，输出A/B的最后一位小数的值，如果A/B是无限循环小数或者是整数则输出0

[样例输入]

1 3
1 2
1 5
2 1

[样例输出]

0
5
2
0

solution

难点是怎么检测出这个分数是无限循环小数。

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

int *map = NULL;
int count = 100; /* 键值对的数量 */

int find_map(int key)
{
        int *buffer = NULL;

        if (key >= count)
        {
                buffer = (int *)malloc(2*key*sizeof(int));
                memset(buffer, 0, 2*key*sizeof(int));

                memcpy(buffer, map, count);
                count = 2 * key;

                if (map)
                        free(map);
                map = buffer;
        }
        return map[key];
}

int solve(int n, const int d)
{
        assert (n < d && n % d);
        int strlen = 1; /* 小数部分的长度 */

        while(1)
        {
                n *= 10;
                int value = find_map(n);
                if (value == 0)
                        map[n] = strlen;
                else
                        return strlen - value;

                if (n < d)
                {
                        strlen++;
                        continue;
                }

                int mod;
                mod = n % d;
                if (mod == 0)
                {
                        printf ("%d\n", n / d); /* 有限小数 */
                        return 0;
                }
                strlen++;
                n = mod;
        }

        return 0;
}

int main(void)
{
        int a, b;
        int ret;

        map = (int *)malloc(count * sizeof(int));
        while(~scanf("%d %d", &a, &b))
        {
                memset(map, 0, count*sizeof(int));
                if (a % b == 0) /* 能够整除 */
                {
                        printf ("0\n");
                        continue;
                }

                ret = solve(a%b, b);
                if (ret > 0)    /* 无限循环小数，返回循环体的长度 */
                {
                        printf ("0\n");
                        continue;
                }
        }

        if (map)
                free(map);
        return 0;
}
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
#include <iostream>
#include <string>
#include <map>
#include <cassert>
#include <cstdio>

using namespace std;

map<int, int> pos;

int solve(int n , const int d, string &ans)
{
        assert(n < d && n % d);
        pos.clear();

        while(1)
        {
                n *= 10;
                int value = pos[n];
                if (value == 0)
                {
                        pos[n] = ans.size();
                } else {
                        return ans.size() - value;
                }

                if (n < d)
                {
                        ans += "0";
                        continue;
                }

                int mod;
                mod = n % d;
                ans += to_string(n/d);
                n = mod;

                if (n == 0)
                {
                        return 0;
                }
        }

        return 0;
}

int main(void)
{
        int a, b;
        while(~scanf("%d %d", &a, &b))
        {
                if (a % b == 0)
                {
                        cout << "0" << endl;
                        continue;
                }

                int ret = 0;
                string ans = to_string(a/b);
                ans += ".";

                ret= solve(a%b, b, ans);
                if (ret > 0)
                {
                        cout << "0" << endl;
                        continue;
                }

                cout << ans.c_str()[ans.size() -1] << endl;
        }

        return 0;
}

从上面代码可以看出，C++版本比较简洁，而C语言版本要自己实现key/value映射，而且没有将小数部分以字符串的形式保存。

Problem-02 幂运算

给定两个值x/y，其取值范围均为[1,1000]，将x作为幂运算的底数值，y作为幂运算的指数值，计算 x^y 的结果。

[输入]

有若干组，每组1 行，每行中包含两个数，分别表示x/y的值，中间使用空格分隔。

[输出]

对于输入的每一行，计算一个结果，输出到一行

[样例输入]

34 56
102 356

[样例输出]

57918773205287127842044254126179599852840968492056164062843692360166371779746690236416
11525536415592716356648444162121164392687163175948295780407329630004551512959186681381273244602190757058373206291554281875540618042949363675225216676477008497546493670298238521544171633524700764806166227229335118687219889267655183448474160653716777369227626785925762359475294959620339306272244056731636176512806213745898010455096462431289370207384844632477617019982790779702457310729047176281759656263753792457270711025862323789528888545602012704194263073614030101358318488028646734547322466415087427024407008549768556431442559106783257516131690451377322649207503242078203428686238550077244853875462845035889887081653722781635654331259153794693134695552882744378661561578545928174213170104944801295608527030096756736

基本数据类型未必能表示幂运算的结果，因此为了表示大数，大数运算也就应运而生。利用数组的连续性，将大数的每一位上的数字单独存放到对应的数组位置上，然后再对每位数字进行基本的加减乘除运算。本题只涉及到大数乘运算，且结果最多只有3000个数字（1000^1000）。

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
#include <stdio.h>
#include <string.h>
#define MAX 3100

int num[10];   //底数
int res[MAX];       //幂运算的结果

void mul(int num[], int pro[], int len)
{
    int s[MAX] = {0};
    int i,j;

    for (i = 0; i < len; i++)
    {
        for (j = 0; j < MAX; j++)
            s[i+j] = s[i+j] + num[i] * res[j];
    }

    for(i = 0; i < MAX; i++)  /* 处理进位 */
    {
        if (s[i] >= 10)
            s[i+1] = s[i+1] + s[i]/10;
        res[i] = s[i]%10;
    }
}

int main(void)
{
    int x, y;
    char str[MAX];
    while(~scanf("%d %d", &x, &y))
    {
        memset(str, 0, sizeof(str));
        memset(num, 0, sizeof(num));
        memset(res, 0, sizeof(res));
        sprintf(str, "%d", x);

        int i,j,k;
        int len = strlen(str);
        for (j=0,k=0,i=len-1; i >= 0; i--)
        {
            num[j++] = str[i]-'0';
            res[k++] = str[i]-'0';
        }

        while(y > 1) /* 自乘次数等于y-1 */
        {
            mul(num, res, len);
            y--;
        }

        for(i = MAX-1; i>0; i--)
            if(res[i])
                break;
        for(; i >= 0; i--)
            printf("%d", res[i]);
        printf("\n");
    }

    return 0;
}

Problem-03 快速幂取模

Problem-04 回文数

给定一个自然数x，若n的各位数字反向排列所得的自然数y与x相等，则称为x为回文数，比如，x=1234321，则x是一个回文数。现在输入一个数，分别判断它以2～16进制的形式呈现时是不是回文数。

[输入]

输入自然数m， 0<m<50000

[输出]

如果存在，以"Number m is palindrom in basis %d"格式输出所有情况；
如果不存在，输出"Number m is not palindrom"

[样例输入]

99

[样例输出]

Number 99 is palindrom in basis 2.
Number 99 is palindrom in basis 10.

solution

对输入自然数取商取余，从而计算出反向排列的数字，最后将计算得到数字与输入数字比较，相等的话说明它就是当前进制下的回文数

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
#include <stdio.h>
#include <string.h>

int palindrom(int x, int basis)
{
	int result=0,n=x;
	while(n)
	{
		result=result*basis+n%basis;
		n/=basis;
	}
	return (result==x);
}

int main(void)
{
	int m, i = 0;
	int record[17];
	int result = 0;
	while(scanf("%d", &m) != EOF)
	{
		if (m < 0 || m >= 50000)
		{
			continue;
		}
		if (!m)
			break;
		
		memset(record, 0x00, sizeof(record));
		result = 0;
		for(i = 2; i <= 16; i++)
		{
			if (palindrom(m, i))
			{
				record[i] = i;
				printf("Number %d is palindrom in basis %d.\n", m, i);
			}
			result += record[i];
		}
		
		if (!result)
			printf("Number %d is not palindrom\n", m);
	}
	
	return 0;
}