算法设计与分析第四章作业

(1)

求2+22+222+2222+…+22…22(不考虑精度)

#include <iostream>
typedef long long LL;
using namespace std;
//快速幂
LL FastPower(LL m,LL n){
    if(n==0) return 1;
    LL res=FastPower(m,n>>1);
    if(n&1) return res*res*m;//奇数就平方再乘以底数
    else return res*res;//偶数就平方
}
int main(){
    LL n;
    cin>>n;
    //求和公式
    cout<<(20*(FastPower(10,n)-1)-n)/81<<endl;
    return 0;
}

时间复杂度:O(log n);

(7)

有一堆棋子，2枚2枚地数，最后余1枚；3枚3枚地数，最后余2枚；5枚5枚的数，最后余4枚；6枚6枚地数，最后余5枚；只有7枚7枚地数，最后正好数完。求这堆棋子最少有多少棋子。

分析

• 最小公倍数=两整数的乘积÷最大公约数
• 2枚2枚的数，最后余1枚，故该棋子是奇数。
• 棋子个数+1是2,、3、5、6的公倍数，故为5、6的公倍数。
• 5、6的最小公倍数是30。
• 棋子个数是7的公倍数。
  综上所知，棋子数n+1是30的公倍数，n是7的公倍数

#include<iostream>
using namespace std;
//Greatest Common Divisor,GCD
//Least Common Multiple, LCM
//欧几里得算法:gcd(a,b)=gcd(b,a%b)
int gcd(int a,int b){
   if(b==0) return a;
   return gcd(b,a%b);
}
//算术基本定理得到gcd(a,b)*lcm(a,b)=a*b
int lcm(int a,int b){
   return a*b/gcd(a,b);
}
int main(){
   int t=lcm(6,lcm(5,lcm(2,3)));
   while(1){
       if((t-1)%7==0){cout<<t<<endl;break;}
       t*=2;
   }
}

(9)

利用分治法求一组数中最大的两个数和最小的两个数