《算法笔记上机实验指南》第4章 入门篇（2）---算法初步 5.6大整数运算

pat A1023

题意：

输入：

1.输入一个大整数

输出：

1.将他翻倍然后看其每个数字位数是否与原数列一致

解题思路：

参考代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
/*
    解题思路：
    1.肯定是有大整数乘法的所有包含函数：1.结构 2.change 3.相乘multi 
    2.最重要的是Judge判断函数，如果翻倍的数的每个数字的个数和原来的一致，则返回true，否则，返回false
    3.根据Judge的值输出yes或者no，最后都要输出翻倍后的数字
*/
struct bign
{
    int d[21];
    int len;
    bign()
    {
        memset(d,0,sizeof(d));
        len=0;
    }
};
bign change(string str)    //将整数转化为bign
{
    bign a;
    a.len=str.length();
    for(int i=0; i<a.len; i++)
    {
        a.d[i]=str[a.len-i-1]-'0';
    }
    return a;
}
bign multi(bign a, int b)  //高精度乘法
{
    bign c;
    int carry=0;   //进位
    for(int i=0; i<a.len; i++)
    {
        int temp=a.d[i]*b+carry;
        c.d[c.len++]=temp%10;         //个位作为该位置的结果
        carry=temp/10;   //高位部分为进位
    }
    while(carry!=0)
    {
        c.d[c.len++]=carry%10;
        carry/=10;
    }
    return c;
}
bool Judge(bign a, bign b)   //判断b的所有是否是a的某个排列
{
    if(a.len != b.len)    //若长度不同，则肯定是false
    {
        return false;
    }

    int count[10]={0};      //计数0---9出现的次数
    for(int i=0; i<a.len; i++)
    {
        count[a.d[i]]++;         //数位a.d[i]对应的count值加1
        count[b.d[i]]--;           //数位b.d[i]对应的count值减1
    }
    for(int i=0; i<10; i++)   //判断0---9出现次数是否都为0
    {
        if(count[i]!=0)  //只要有一个数字出现次数不为0；则返回false
        {
            return false;
        }

    }
    return true;       //返回true
}
void print(bign a)  //输出bign
{
    for(int i=a.len-1; i>=0; i--)
    {
        printf("%d",a.d[i]);
    }
}
int main()
{
    string str;
    cin >> str;  //输入数据
    bign a=change(str);   //转化为bign
    bign mul=multi(a,2);    //计算a*2
    if(Judge(a,mul)==true)
        printf("Yes\n");
    else
        printf("No\n");
    print(mul);
    return 0;
}

---

pat A1024

题意：

输入：

1.输入数字n
2.输入操作次数

输出：

1.如果在指定操作次数内有会问数，则输出该回文数和操作次数
2.如果在指定次数内没有回文数，则输出最后的操作后的结果和操作次数

解题思路：

参考代码：

#include<iostream>
#include<cstring>
#include<algorithm>
/*
    解题思路：
    1.大整数的加法运算的各种函数
    2.回文数判断函数：
        1.对于一个数组而言，a[i]?=a[len-i-1]就是判断第一个数对应倒数第一个；第二个对应倒数第2个以此类推
        2.一旦有不同，返回false
        3.最后返回true
    3.main函数中的while循环逻辑：当不是回文数且操作次数小于k时，执行下面语句：
        1.bign b=a;
        2.扭转a
        3.add(a,b)
        4.操作次数++
    4.最后，输出a和操作次数，这里给出几个特殊的情况看下：
        1.如果一输入的是回文数，则直接输出该数字和0
        2.如果操作次数达到了k次，循环结束；那么就直接输出最后的和，如下图：63 3的例子
        3.如果已经是回文数，输出该回文数，和对应次数，如下图 67 3的例子
*/
using namespace std;
struct bign
{
    int d[1000];
    int len;
    bign()
    {
        memset(d,0,sizeof(d));
        len=0;
    }
};
bign change(string str)
{
    bign c;
    c.len=str.length();
    for(int i=0; i<c.len; i++)
        c.d[i]=str[c.len-i-1]-'0';
    return c;
}
bign add(bign a, bign b)
{
    int carry=0;
    bign c;
    for(int i=0; i<a.len || i<b.len; i++)
    {
        int temp=a.d[i]+b.d[i]+carry;
        c.d[c.len++]=temp%10;
        carry=temp/10;
    }
    if(carry!=0)
        c.d[c.len++]=carry;
    return c;
}
bool Judge(bign a)        //简单的一个回文数判断
{
    for(int i=0; i<a.len; i++)
        if(a.d[i]!=a.d[a.len-i-1])
            return false;
    return true;
}
int main()
{
    string n;
    int k,c=0;
    cin >> n >> k;
    bign a=change(n);
    while(c<k && !Judge(a))            //如果不是回文数，且操作次数不超过k次，则先逆转后相加
    {
        bign b=a;
        reverse(a.d,a.d+a.len);
        a=add(a,b);
        c++;
    }
    for(int i=a.len-1; i>=0; i--)
        cout << a.d[i];
    cout << endl;
    cout << c;
    return 0;
}

知识总结：

1.对于数组的扭转reverse(a,a+长度) //a表示数组名

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int main()
{
    int a[2];
    a[0]=1;
    a[1]=2;
    reverse(a,a+2);
    cout << a[0] << " " << a[1];
    return 0;
}

2.对于回文数的判断

a[i]==a[len-i-1]  //len表示a字符串的长度

本文地址：https://blog.csdn.net/wsfhdhjs/article/details/107215926