欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-07-07 20:10:34
pat A1023题意:输入: 1.输入一个大整数输出: 1.将他翻倍然后看其每个数字位数是否与原数列一致解题思路:参考代码:#include#include#includeusing namespace std;/* 解题思路: 1.肯定是有大整数乘法的所有包含函数:1.结构 2.change 3.相乘multi 2.最重要的是Judge判断函数,如果翻倍的数的每...

pat A1023

题意:

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

输入:

1.输入一个大整数

输出:

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

解题思路:

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

参考代码:

#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

题意:

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

输入:

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

输出:

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

解题思路:

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

参考代码:

#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