蓝桥杯练习-3.12

代码练习

• 高精度加法

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。

算法描述

由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。
　　定义一个数组A，A[0]用于存储a的个位，A[1]用于存储a的十位，依此类推。同样可以用一个数组B来存储b。
　　计算c = a + b的时候，首先将A[0]与B[0]相加，如果有进位产生，则把进位（即和的十位数）存入r，把和的个位数存入C[0]，即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加，这时还应将低位进上来的值r也加起来，即C[1]应该是A[1]、B[1]和r三个数的和．如果又有进位产生，则仍可将新的进位存入到r中，和的个位存到C[1]中。依此类推，即可求出C的所有位。
　　最后将C输出即可。

输入格式

输入包括两行，第一行为一个非负整数a，第二行为一个非负整数b。两个整数都不超过100位，两数的最高位都不是0。

输出格式

输出一行，表示a + b的值。

样例输入

20100122201001221234567890
2010012220100122

样例输出

20100122203011233454668012

代码实现

#include <stdio.h>
#include<string.h>
int main()
{
    int i,alen,blen,n;
	char a[101], b[101], c[103];//对应存两个加数和 和的字符数组，因为数字太大了，只能换为字符存储
	memset(c,0,sizeof(c));//清零
    scanf("%s%s", a, b);
     alen = strlen(a);
     blen = strlen(b);
    if (alen >= blen)//得到较大的那个长度，当作循环条件
    {
        n = alen;
    }
    else n = blen;
    for (i = 0; i < n; i++)
    {
        if (i < alen)
            c[i] += a[alen-i-1] - '0';//因为是字符，所以需要减去字符0，得到的ASCII码就是对应的数，而且是从低位开始加起，所以数组从倒着的开始
        if (i < blen)
            c[i] += b[blen-i-1] - '0';
        if (c[i] >= 10)
        {
            c[i+1] = c[i] / 10;//如果加起来大于10，要向高位进位
            c[i] %= 10;//然后本位得到余下的
        }
    }
    if (c[n] != 0)
    {
        for (i = n; i >= 0; i--)//倒着输出便是和
        printf("%d", c[i]);
    }
    else
    {
        for (i = n - 1; i >= 0; i--)//倒着输出便是和
        printf("%d", c[i]);
    }
    return 0;
}

❕注意：C++中，全局阈只能声明、初始化变量； 不能用于赋值、运算、调用函数等！！！也要注意，当两数都是相同位数时，最后输出的时候就不是n位了，而是n+1位

• 阶乘运算

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

输入一个正整数n，输出n!的值。
　　其中n!=1 *2 * 3… * n。

算法描述

n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
　　将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
　　首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。

输入格式

输入包含一个正整数n，n<=1000。

输出格式

输出n!的准确值。

思路

根据算法描述，我们构建一个足够大的数组来存放这个大数的每一位，然后，我们用一个for循环来循环我们要乘的数，因为数每一位（个位，十位，百位…）都要乘，所以要有第二个循环，来循环每一个数组元素，这里需要用到进位，我们在每一轮乘数的开始，把进位初始为0，数组当前开到的最大下标记为high = 0，我们每一组元素乘完i再加上低位的进位以后，只需%10保留个位填到当前数组下标即可，然后进位数/10，一直到数组最大下标，如果这个时候进位数还有，就说明要开数组了，因为总数的位数又增加了。

代码实现：

#include <iostream>
using namespace std;
const int N = 100000;
int a[N];
int n;
int main()
{
    cin >> n;
    a[0] = 1;
    int r;//r代表进位数
    int high = 0;//high表示现在数组开到第几位了,第一次为0
    for (int i = 2; i <= n; i++)//从2开始乘
    {
        r = 0;//每乘完一个数后，进位都初始化为0
        for (int j = 0; j <= high; j++)
        {
            int mul = a[j] * i + r;
            a[j] = mul % 10;//当前位数保留个位的
            r = mul / 10;//进位,这里不用担心进位是很大的数怎么办，因为我们只是先把数组填满，多出来的肯定位数已经大过了数组上界high，没有影响
        }
        while(r)//因为进位可能不是一个个位数，所以当当前可以开到的最大数组个数都被填满数字了以后，
                //进位仍然不为0，就继续开拓数组，把进位一个个往后面填上
        {
            a[++high] = r % 10;
            r /= 10;
        }
    }
    for (int i = high; i >= 0; i--)
    {
        cout << a[i];
    }
    return 0;
}

• G 螺旋折线（第九届蓝桥杯）

Description

如图p1.png所示的螺旋折线经过平面上所有整点恰好一次。

对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。

例如dis(0, 1)=3, dis(-2, -1)=9

给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？

Input

X和Y

对于40%的数据，-1000 <= X, Y <= 1000

对于70%的数据，-100000 <= X， Y <= 100000

对于100%的数据, -1000000000 <= X, Y <= 1000000000

Output

输出dis(X, Y)

思路

**
**

先分别找出y>0黄点的坐标变化规律，再找出y<0黄点的坐标变化规律。

当x的绝对值大于y的绝对值时也就是dis点在竖着的折现上时，都要用x轴上方黄色的点来计算。

当x的绝对值小于y的绝对值时也就是dis点在横着的折现上时，用x轴下方黄色的点来计算。

当y等于0也就是dis点在x轴上时单独计算。

代码实现（不完全对）：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long dis(long long x, long long y)
{
    if(x == 0)
    {
        if (y > 0)  return pow((2 * y), 2) - y;
        else if (y < 0)  return pow((2 * y), 2) - y + 4 * y;
        else if (y == 0)  return 0;
    }
    else if (x > 0)
    {
        if (y == 0)
        {
            return pow((2 * x), 2) + x;
        }
        else if (y > 0)
        {
            if (y == x)  return pow((2 * x), 2);
            else if (y < x)  return pow((2 * x), 2) + x - y;
            else if (y > x)  return pow((2 * y), 2) - y + x;
        }
        else if (y < 0)
        {
            if (abs(y) == x)  return pow((2 * x), 2) + 2 * x;
            else if (abs(y) < x)  return pow((2 * x), 2) + 2 * x - (x + y);
            else if (abs(y) > x)  return pow((2 * y), 2) - y + 4 * y - x;
        }
    }
    else if (x < 0)
    {
        if (y == 0)
        {
            return pow((2 * x), 2) + 2 * x + x;
        }
        else if (y > 0)
        {
            if (y == abs(x))
            {
                return pow((2 * x), 2) + 2 * x;
            }
            if (y < abs(x))  return pow((2 * x), 2) + 2 * x + x + y;
            if (y > abs(x))  return pow((2 * y), 2) - y + x;
        }
        else if (y < 0)
        {
            if ((abs(x) - abs(y)) == 1)  return pow((2 * y), 2) + y - 4 * y - x;
            else if (abs(y) < abs(x))  return pow(2 * (x + 1), 2) - 5 * (x + 1) + 1 + y;
            else if (abs(y) >= abs(x))  return (4 * abs(y) + 3) * abs(y) + abs(x);
        }
    }
}
int main()
{
    long long x, y;
    scanf("%lld%lld",&x, &y);
    printf("%lld\n",dis(x, y));
    return 0;
}

❕注意：注意函数类型为long long，传入的参数类型也为long long