算法笔记_第五章

第五章书上的题目+Codeup+上机训练

5(书)

5.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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

//PAT B1019
int num[5];

void to_array(int n,int num[])
{
    for(int i=0;i<4;i++){
        num[i]=n%10;   //低位存放低位
        n/=10;
    }
}

int to_num(int num[])
{
    int result=0;
    for(int i=0;i<4;i++){
        result=result*10+num[i];
    }
    return result;
}

bool cmp(int a,int b)
{
    return a>b;
}

int main()
{
    int n,MIN,MAX;
    scanf("%d",&n);
    while(true){
        to_array(n,num);
        sort(num,num+4);
        MIN=to_num(num);
        sort(num,num+4,cmp);  //increasing
        MAX=to_num(num);
        n=MAX-MIN;
        printf("%04d - %04d = %04d\n",MAX,MIN,n);
        if(n==6174||n==0) break;
    }
    return 0;
}

5.4

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

//PAT B1013
int prime[1000001];
bool p[1000001]={0};
int pnum=0;

void FindPrime()
{
    for(int i=2;i<1000001;i++){
        if(p[i]==false){
            prime[pnum++]=i;
            for(int j=i*2;j<1000001;j+=i){
                p[j]=true;
            }
        }
    }
    return;
}

int main()
{
    int N,M;
    scanf("%d%d",&N,&M);
    FindPrime();
    int count=0;
    for(int i=N;i<=M;i++){
        printf("%d",prime[i-1]);
        count++;
        if(i<M && count%10!=0) printf(" ");
        if(count%10==0 && i<M) printf("\n");
    }
    return 0;
}

5.5

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

//PAT A1059
int prime[100001];
bool p[100001]={0};
int pnum=0;

void FindPrime()
{
    for(int i=2;i<100001;i++){
        if(p[i]==false){
            prime[pnum++]=i;
            for(int j=i*2;j<100001;j+=i){
                p[j]=true;
            }
        }
    }
    return;
}

struct factor
{
    int x,cnt;
}fac[10];

int main()
{
    FindPrime();
    int n;
    scanf("%d",&n);
    int num=0;
    if(n==1) printf("1=1");
    else{
        printf("%d=",n);
        int sqr=(int)sqrt(1.0*n);
        for(int i=0;i<pnum&&prime[i]<=sqr;i++){
            if(n%prime[i]==0){
                fac[num].x=prime[i];
                fac[num].cnt=0;
                while(n%prime[i]==0){
                    fac[num].cnt++;
                    n/=prime[i];
                }
                num++;
            }
            if(n==1) break;
        }
        if(n!=1){
            fac[num].x=n;
            fac[num++].cnt=1;
        }
        for(int i=0;i<num;i++){
            if(i>0) printf("*");
            printf("%d",fac[i].x);
            if(fac[i].cnt>1){
                printf("^%d",fac[i].cnt);
            }
        }
    }
    return 0;
}

5(上机)

5.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
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

//PAT A1049
//这题对数学要求很高，自己推一编，然后先记住结论就好
int main()
{
    int n;
    scanf("%d",&n);
    int ans=0;
    int now,left,right;
    int idx=1;
    while(n/idx!=0){
        left=n/(idx*10);
        now=n/idx%10;
        right=n%idx;
        if(now==0){
            ans+=left*idx;
        }
        else if(now==1){
            ans+=left*idx+right+1;
        }
        else{
            ans+=(left+1)*idx;
        }
        idx*=10;
    }
    printf("%d",ans);
    return 0;
}

/*
//PAT A1008
int main()
{
    int N;
    scanf("%d",&N);
    int ans=0,temp,last=0;
    while(N--){
        scanf("%d",&temp);
        if(temp>last){
            ans+=(temp-last)*6;
            ans+=5;
            last=temp;
        }
        else if(temp<last){
            ans+=(last-temp)*4;
            ans+=5;
            last=temp;
        }
        else{
            ans+=5;
        }
    }
    printf("%d",ans);
    return 0;
}
*/

/*
//PAT B1003
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        char s[105];
        int cnt_p = 0, cnt_t = 0, other = 0;
        int flag_p, flag_t;
        scanf("%s",s);
        int len = strlen(s);
        for(int i = 0; i < len; i++)
        {
            if(s[i] == 'P')
            {
                cnt_p++;    //记录P的个数
                flag_p = i;   //标记P位置
            }
            else if(s[i] == 'T')
            {
                cnt_t++;    //记录T的个数
                flag_t = i;   //标记T位置
            }
            else if(s[i] != 'A'){
                other++;
            }
        }
        if((cnt_p != 1) || (cnt_t != 1) || other || (flag_t - flag_p <= 1))
            printf("NO\n");
        else if(flag_p * (flag_t-flag_p-1) == len - flag_t - 1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
*/

/*
//PAT B1049
int main()
{
    int n;
    scanf("%d",&n);
    double ans,temp;
    for(int i=1;i<=n;i++){
        scanf("%lf",&temp);
        ans+=temp*i*(n+1-i);
    }
    printf("%.2f",ans);
    return 0;
}
*/

5.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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

using namespace std;

//const int CLK_TCK=100;

//PAT B1008
int main()
{
    int N=0,M=0;
    int A[200];
    scanf("%d%d",&N,&M);
    M=M%N;
    for(int i=0;i<N;i++){
        scanf("%d",&A[i]);
    }
    for(int i=N-M;i<N;i++){
        printf("%d ",A[i]);
    }
    for(int i=0;i<N-M-1;i++){
        printf("%d ",A[i]);
    }
    printf("%d",A[N-M-1]);
    return 0;
}

5.3

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

//PAT B1034
struct Fraction{
    long long up,down;
};

long long gcd(long long a,long long b)
{
    if(b==0) return a;
    else{
        gcd(b,a%b);
    }
}

Fraction reduce(Fraction a)
{
    if(a.up==0) a.down=1;
    else{
        int temp=gcd(abs(a.up),abs(a.down));
        a.up/=temp;
        a.down/=temp;
    }
    return a;
}

Fraction add(Fraction a,Fraction b)
{
    Fraction result;
    result.up=a.up*b.down+b.up*a.down;
    result.down=a.down*b.down;
    return reduce(result);
}

Fraction sub(Fraction a,Fraction b)
{
    Fraction result;
    result.up=a.up*b.down-b.up*a.down;
    result.down=a.down*b.down;
    return reduce(result);
}

Fraction multiply(Fraction a,Fraction b)
{
    Fraction result;
    result.up=a.up*b.up;
    result.down=a.down*b.down;
    return reduce(result);
}

Fraction divide(Fraction a,Fraction b)
{
    Fraction result;
    result.up=a.up*b.down;
    result.down=a.down*b.up;
    if(result.down<0){
        result.down=-result.down;
        result.up=-result.up;
    }
    return reduce(result);
}

void output(Fraction result)
{
    result=reduce(result);
    if(result.up<0) printf("(");
    if(result.down==1) printf("%lld",result.up);
    else if(abs(result.up)>abs(result.down)){
        printf("%lld %lld/%lld",result.up/result.down,abs(result.up)%result.down,result.down);
    }
    else{
        printf("%lld/%lld",result.up,result.down);
    }
    if(result.up<0) printf(")");
    return;
}

int main()
{
    Fraction a,b;
    scanf("%lld/%lld %lld/%lld",&a.up,&a.down,&b.up,&b.down);
    output(a);
    printf(" + ");
    output(b);
    printf(" = ");
    output(add(a,b));
    printf("\n");

    output(a);
    printf(" - ");
    output(b);
    printf(" = ");
    output(sub(a,b));
    printf("\n");

    output(a);
    printf(" * ");
    output(b);
    printf(" = ");
    output(multiply(a,b));
    printf("\n");

    output(a);
    printf(" / ");
    output(b);
    printf(" = ");
    if(b.up==0) printf("Inf");
    else output(divide(a,b));
    printf("\n");
    return 0;
}

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

//PAT A1081
struct Fraction{
    long long up,down;
};

long long gcd(long long a,long long b)
{
    if(b==0) return a;
    else{
        gcd(b,a%b);
    }
}

Fraction reduce(Fraction a)
{
    if(a.up==0) a.down=1;
    else{
        int temp=gcd(abs(a.up),abs(a.down));
        a.up/=temp;
        a.down/=temp;
    }
    return a;
}

Fraction add(Fraction a,Fraction b)
{
    Fraction result;
    result.up=a.up*b.down+b.up*a.down;
    result.down=a.down*b.down;
    return reduce(result);
}

void output(Fraction result)
{
    reduce(result);
    if(result.down==1) printf("%lld",result.up);
    else if(abs(result.up)>result.down) printf("%lld %lld/%lld",result.up/result.down,abs(result.up)%result.down,result.down);
    else{
        printf("%lld/%lld",result.up,result.down);
    }
    return;
}

int main()
{
    int n;
    scanf("%d",&n);
    Fraction sum,temp;
    sum.up=0;
    sum.down=1;
    for(int i=0;i<n;i++){
        scanf("%lld/%lld",&temp.up,&temp.down);
        sum=add(sum,temp);
    }
    output(sum);
    return 0;
}

5.4

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

//PAT A1015
bool isPrime(int n)
{
    if(n<=1) return false;
    int sqr=(int)sqrt(1.0*n);
    for(int i=2;i<=sqr;i++){
        if(n%i==0) return false;
    }
    return true;
}

int main()
{
    int n,radix;
    int temp[120];
    while(scanf("%d",&n)!=EOF){
        if(n<0) break;
        scanf("%d",&radix);
        if(isPrime(n)==false) printf("No\n");
        else{
            int len=0;
            do{
                temp[len++]=n%radix;
                n/=radix;
            }while(n!=0);
            for(int i=0;i<len;i++){
                n=n*radix+temp[i];
            }
            if(isPrime(n)==true) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

/*
//PAT B1007
int prime[100001];
bool p[100001]={0};
int pnum=0;

void FindPrime()
{
    for(int i=2;i<100001;i++){
        if(p[i]==false){
            prime[pnum++]=i;
            for(int j=i*2;j<100001;j+=i){
                p[j]=true;
            }
        }
    }
    return;
}

int main()
{
    int N;
    scanf("%d",&N);
    FindPrime();
    int pair=0;
    for(int i=1;i<100001;i++){
        if(prime[i]>N) break;
        if(prime[i]-prime[i-1]==2){
            pair++;
        }
    }
    printf("%d",pair);
    return 0;
}
*/

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>

using namespace std;

//PAT A1078
bool isPrime(int n)
{
    if(n<=1) return false;
    int sqr=(int)sqrt(1.0*n);
    for(int i=2;i<=sqr;i++){
        if(n%i==0) return false;
    }
    return true;
}

const int N=10001;
bool HashTable[N]={0};

int main()
{
    int msize,n;
    scanf("%d%d",&msize,&n);
    while(isPrime(msize)==false) msize++;
    int temp;
    for(int i=0;i<n;i++){
        scanf("%d",&temp);
        int pos=temp%msize;
        if(HashTable[pos]==false){
            HashTable[pos]=true;
            if(i==0) printf("%d",pos);
            else printf(" %d",pos);
        }
        else{
            int step;
            for(step=1;step<msize;step++){
                pos=(temp+step*step)%msize;
                if(HashTable[pos]==false){
                    HashTable[pos]=true;
                    if(i==0) printf("%d",pos);
                    else printf(" %d",pos);
                    break;
                }
            }
            if(step>=msize){
                if(i>0) printf(" ");
                printf("-");
            }
        }
    }
    return 0;
}

5.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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
#include<string.h>

//PAT B1017
struct bign {
    int d[1010];
    int len;
    bign() {
        memset(d, 0, sizeof(d));
        len = 0;
    }
};
bign change(char str[]) { // 将整数转换为bign
    bign a;
    a.len = strlen(str);
    for(int i = 0; i < a.len; i++) {
        a.d[i] = str[i] - '0'; // 高位放进a的低位
    }
    return a;
}

void divide(bign a, int b, int& r) { //高精度除法，r为余数
    bign c;
    c.len = a.len;
    for(int i = 0; i < a.len; i++) { //从高位开始
        r = r * 10 + a.d[i]; //和上一位遗留的余数组合
        if( r < b ) c.d[i] = 0; //不够除，该位为0
        else { //够除
            c.d[i] = r / b; //商
            r = r % b; //获得新的余数
        }
    }
    int j = 0;
    for(int i = 0; i < c.len - 1 && c.d[i] == 0; i++) {
        j++;
    }

    // 遍历输出
    for(int i = j; i < c.len; i++)
        printf("%d", c.d[i]);
    printf(" %d", r);
}

int main() {
    char str[1010];
    int b = 0, r = 0;
    scanf("%s%d", str, &b);
    bign a = change(str); //将a转换为bign型
    divide(a, b, r);
    return 0;
}
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
//和上面一题差不多，懒得做了，转载自https://blog.csdn.net/linghugoolge/article/details/82825757
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	//read
	string s, t="";
	cin >> s ;
 
	//solve the original number
	int a[10] = {0};
	for (int i = 0; i < s.length(); ++i) 
		a[s[i] - '0'] ++ ;
 
	//double the number
	reverse(s.begin(), s.end());
	int jin = 0;
	for (int i = 0; i < s.length(); ++i) {
		int b = jin + 2*(s[i] - '0');
		t += (char)(b % 10 + '0');
		jin = b / 10;
	}
	if (jin != 0)
		t += (char)(jin + '0');
	reverse(t.begin(), t.end());
 
	//solve the second number
	for (int i = 0; i < t.length(); ++i) 
		a[t[i] - '0']--;
	
	//result
	bool flag = true;
	for (int i = 0; i < 10; ++i) {
		if (a[i] != 0) {
			flag = false;
			break;
		}
	}
	if (flag == true)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	cout << t << endl;
 
	system("pause");
	return 0;
}
本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2020/02/04/%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-%E7%AC%AC%E4%BA%94%E7%AB%A0/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 本站访客数人

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

记录成长的点滴<br><br>涉猎颇广的信息技术爱好者<br>希望未来的xiaoyuyu<br>可以成为优秀的工程师