数学基础

引导问题:整数求和

任务:

给定一个正整数n,请计算1+2+3+…+n的结果,其中n<=50000.

​ Sample input:

​ 10

​ Sample output:

​ 55

常见实现方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <stdio.h>

int main()
{
int n, i, sum;
while (scanf("%d", &n) == 1)
{
sum = 0;
for (i = 1; i <= n; i++)
sum += i;
printf("%d\n\n", sum);
}
return 0;
}

引导问题:其他方法?

SUM(n)=1+2+3+…+n

​ =n*(n+1)/2

当n=50000时,n*n(n+1)爆int

例1

任务:

给定两个正整数,计算这两个数的最小公倍数。

样例输入:

10 14

4 6

样例输出:

70

12

思考: LCM(A,B)=A*B/GCD(A,B) 注意A * B 爆int

  • LCM最小公倍数

  • GCD最大公约数(辗转相除法)

  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int gcd(int big,int small)
    {
    int temp;
    while(small!=0)
    {
    temp=big%small;
    big=small;
    small=temp;
    }
    return big;
    }
  • 可以改成A/GCD(A,B)*B

例2

任务:

给定一个正整数N,请计算N个N相乘的结果的个位数是多少(1<=N<=1,000,000,000).

Sample Input

3

Sample Output

7

数据规模->很大

暴力方法->该打

基本思路-> ==规律==(循环节)

例3

任务:

有一种fibonacci数列,定义如下:

F(0) = 7,

F(1) = 11,

F(n) = F(n-1) + F(n-2) (n>=2).

给定一个n(n<1,000,000),请判断F(n)能否被3整除,输出yes和no

思路:每一项对3求余相加找循环节

例4

任务

求A^B的最后三位数表示的整数(1<=A,B<=100,000,000)

Sample Input

2 3

12 6

Sample Output

8

984

  • 快速幂运算(递归实现)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int power(int a,int n)
    {
    int ans;
    if(n==0) ans=1;
    else
    {
    ans=power(a*a,n/2);
    if(n%2==1) ans*=a;
    }
    return ans;
    }
  • 快速幂运算(非递归实现)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int power(int a,int n)
    {
    int ans=1;
    while(n)
    {
    if(n%2) ans*=a; //奇数情况
    a*=a; //底数平方
    n/=2; //指数减半
    }
    return ans;
    }
  • 由于a^n的值一般都很大,有可能超过int上限,一般会和取模一起计算

例5

任务:

给出若干个元素(可以很多)有序的整数,请查找某个元素是否存在,比如 ——

2 3 4 5 6 8 12 20 32 45 65 74 86 95 100

​ 请查找以上数列中是否存在某个整数(比如25)

  • 二分查找(循环实现)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int BiSearch(int a[],int n,int x)
    {
    //待查数组 范围(结束下标) 待查数字
    int left=0.right=n-1;
    while(left<=right)//等号不能少
    {
    int middle=(left+right)/2;//获得中间下标
    if(a[middle]==x)
    return middle;//找到x返回下标
    if(x>a[middle]) //比中指大
    left=middle+1;
    else //比中值小
    right=middle-1;
    }
    return -1;//未找到
    }
  • 二分查找(递归实现)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int BiSearch(int a[],int x,int left,int right)
    {
    if(left>right)//不能有等号
    return -1;
    else
    {
    int mid=(left+right)/2;//中间下标
    if(a[mid]==x)
    return mid;
    else if(x>a[mid])
    return BiSearch(a,x,mid+1,right);
    else
    return BiSearch(a,x,left,mid-1);
    }
    }

例6

任务:

给出方程: 8x^4^+7x^3^+2x^2^+3x+6=Y

其中,实数Y满足(fabs(Y)<=1e10)

请输出x在区间[0,100]的解,精确到小数点后4位。

  • 只要是连续的,且满足单调性,都可以二分
  • ==2^10^=1024 ,2^20^>1000,000== 二分法速度极快

例7

任务:

给出函数:F(x)=6x^7^+8x^6^+7x^3^+5x^2^-y*x

其中,实数y满足(0<y<le10)

请输出x在取键[0,100]时函数F(x)的最小值,结果精确到小数点后四位

题目分析

  • 指定区间是否满足单调性
  • 显然不满足->不能直接二分法
  • 满足凸性?
  • 如何证明?
  • 极值点的特点
  • 是否可以二分

三分查找

  • 经过求导后和例6变为同一题型
  • 三分查找的前提——数据的==凸性==

例题答案

==答案仅供参考== ==答案仅供参考== ==答案仅供参考==

  • 例1

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

    int gcd(int big, int small)
    {
    int temp;
    while (small != 0)
    {
    temp = big % small;
    big = small;
    small = temp;
    }
    return big;
    }

    int lcm(int x, int y)
    {
    return x / gcd(x, y) * y;
    }

    int main()
    {
    int x, y;
    while (~scanf("%d %d", &x, &y))
    {
    printf("%d\n", lcm(x, y));
    }
    return 0;
    }
  • 例2

    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
    #include <stdio.h>
    int main()
    {
    int n;
    scanf("%d", &n);
    int temp = n % 10;
    int temp2;
    if (temp == 0)
    {
    printf("0");
    }
    else if (temp == 1)
    {
    printf("1");
    }
    else if (temp == 2)
    {
    temp2 = n % 4;
    if (temp2 == 1)
    printf("2");
    else if (temp2 == 2)
    printf("4");
    else if (temp2 == 3)
    printf("8");
    else if (temp2 == 4)
    printf("6");
    }
    else if (temp == 3)
    {
    temp2 = n % 4;
    if (temp2 == 1)
    printf("3");
    else if (temp2 == 2)
    printf("9");
    else if (temp2 == 3)
    printf("7");
    else if (temp2 == 4)
    printf("1");
    }
    else if (temp == 4)
    {
    temp2 = n % 4;
    if (temp2 == 1)
    printf("4");
    else if (temp2 == 2)
    printf("6");
    }
    else if (temp == 5)
    {
    printf("5");
    }
    else if (temp == 6)
    {
    printf("6");
    }
    else if (temp == 7)
    {
    temp2 = n % 4;
    if (temp2 == 1)
    printf("7");
    else if (temp2 == 2)
    printf("9");
    else if (temp2 == 3)
    printf("3");
    else if (temp2 == 4)
    printf("1");
    }
    else if (temp == 8)
    {
    temp2 = n % 4;
    if (temp2 == 1)
    printf("8");
    else if (temp2 == 2)
    printf("4");
    else if (temp2 == 3)
    printf("2");
    else if (temp2 == 4)
    printf("6");
    }
    else if (temp == 9)
    {
    printf("1");
    }
    return 0;
    }
  • 例3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include <stdio.h>
    int main()
    {
    int n;
    scanf("%d", &n);
    if (n % 8 == 3 || n % 8 == 7)
    printf("YES");
    else
    printf("NO");
    return 0;
    }
  • 例4

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include <stdio.h>

    int power(int a,int b)
    {
    int ans=1;
    while(b)
    {
    if(b%2) ans= ans%1000*a;
    a = a*a;
    b /= 2;
    }
    return ans%1000;
    }

    int main()
    {
    int a, b;
    while(~scanf("%d %d",&a,&b))
    {
    printf("%d\n",power(a, b));
    }
    return 0;
    }
  • 例6

    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
    #include  <bits/stdc++.h>
    using namespace std;
    double f(double x)
    {
    return 8 * pow(x, 4.0) + 7 * pow(x, 3.0) + 2 * pow(x, 2.0) + 3 *x + 6;
    }

    int main()
    {
    double Y;
    double left, right, mid;
    int t;
    scanf("%d", &t);
    while (t--)
    {
    scanf("%lf", &Y);
    if (f(0) <= Y && Y <= f(100))
    {
    left = 0;
    right = 100;
    while (right - left > 1e - 6)
    {
    mid = (left + right) / 2;
    double ans = f(mid);
    if (ans > Y)
    right = mid - 1e - 6;
    else
    left = mid + 1e - 6;
    }
    printf("%.4f\n", (left + right) / 2);
    }
    else
    printf("No solition!\n");
    }
    return 0;
    }