CINTA hw1-526互联

1

点击查看代码

#include<iostream>

using namespace std;

int multiply(int a, int b) 
{
    int result = 0;
    while (b > 0) 
    {
    
        if (b % 2 == 0) 
        {
            a *= 2;
            b /= 2;
        } 
        else 
        {
            result += a; 
            a *= 2;
            b /= 2;
        }
    }
    return result; 
}

int main() 
{
    int a;
    int b;
    cin>>a>>b;
    int res = multiply(a, b);
    cout << "The result is: " << res << endl;
	system("pause");
    return 0;
}

运行结果

2

证明定理1.1：对任意给定的整数 a 和 b，其中 b > 0，存在唯一的整数对 q（商）和 r（余数）使得a = qb + r,且 0 ≤ r < b。

证明（数学归纳法）：
① a=0 时，存在q=0，r=0满足条件。
② a=k 时，设存在唯一的整数对 q_k和 r_k 使得a = q_kb + r_k 。
证明a=k+1时，存在唯一的整数对q_k+1与r_k+1使上式依旧成立。
由a = qb + r有k+1=qb+r，得qb=k+1-r。
由假设（存在唯一的整数对 q_k和 r_k 使得a = q_kb + r_k ）有q_kb=k+1-r_k。
由此证明了a=k+1的时候存在唯一的整数对q_k,r_k满足该定理。
得证。

3

用C语言编程实现一种迭代版本的gcd算法和一种egcd算法。利用 gcd算法，写程序完成以下函数的功能。输入:一个正整数n;输出:大于等于1，小于n，且与n互素的正整数的个数。

点击查看代码

#include<iostream>

using namespace std;

int gcd(int a, int b) 
{
    while (b != 0) 
	{
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}
void egcd(int a, int b, int &x, int &y) 
{
    if (b == 0) 
	{
        x = 1;
        y = 0;
        return;
    }
    egcd(b, a % b, y, x);
    y -= a / b * x;
}

int primes(int n) 
{
    int count = 0;
    for (int i = 2; i < n; i++) 
	{
        if (gcd(i, n) == 1) 
		{
            count++;
        }
    }
    return count;
}

int main() 
{
    int n;
    cout << "请输入一个正整数n：";
    cin >> n;
    int result = primes(n);
    cout << "小于" << n << "的与n互质的正整数个数为：" << result+1 << endl;
	system("pause");
    return 0;
}

点击查看图片