2023年秋季学期《算法分析与设计》练习15 OJ-1424 算法分析与设计练习15，使用python、C语言

又一道简单题

题目描述

输入一个四个数字组成的整数 n，你的任务是数一数有多少种方法，恰好修改一个数字，把它 变成一个完全平方数（不能把首位修改成 0）。比如 n=7844，有两种方法：3844=622?和 7744=882。?

输入

输入第一行为整数 T (1<=T<=1000)，即测试数据的组数，以后每行包含一个整数 n (1000<=n<=9999)。?

输出

对于每组数据，输出恰好修改一个数字，把 n变成完全平方数的方案数

样例输入?Copy

2
7844
9121

样例输出?Copy

Case 1: 2
Case 2: 0

import math

def solve(index, t):
    count = 0
    for i in range(1, 5):   # (1,4)
        a = 10 ** (4 - i)
        if i == 1:
            for j in range(1, 10):
                if j == t // a:
                    continue
                b = t - (t // a) * a + j * a
                c = int(math.sqrt(b))
                if c * c == b:
                    count += 1
        else:
            for j in range(10):
                if j == (t % (a * 10)) // a:
                    continue
                b = t - (t % (a * 10)) // a * a + j * a
                c = int(math.sqrt(b))
                if c * c == b:
                    count += 1
    print(f"Case {index + 1}: {count}")

while True:
    n = int(input())
    count = 0
    for i in range(n):
        t = int(input())
        solve(i, t)

自守数

题目描述

自守数是指一个数的平方的尾数等于该数自身的自然数。例如：25^2 =?625，76^2 =?5776，9376^2 =?87909376。请求出n以内的自守数的个数。

输入

int型整数。

输出

n以内自守数的数量。

样例输入?Copy

2000

样例输出?Copy

8

#include <stdio.h>

int is_num(long a) {
    long s = a * a;
    while (a != 0) {
        if (a % 10 != s % 10) {
            return 0; 
        }
        a = a / 10;
        s = s / 10;
    }
    return 1; 
}

int main() {
    long a;
    while (~scanf("%ld", &a)) {
        int count = 0;
        for(int i = a; i >= 0; i--) {
            if (is_num(i)) {
                count++;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

相聚HNUCM校园食堂

题目描述

HNUCM的食堂重新装修了，小明决定约上朋友去食堂相聚，在食堂里，小明看到了M位男同学，N位女同学，小明是一个颜值控，因此他对每一位男生和女生都有一个颜值打分，他心里yy着想为这些单身狗们进行配对，小明真是一个关心同学的人！但小明认为配对同学的颜值之差不能超过5，注意必须是一位男同学和一位女同学才能配对，虽然小明对于可以配对的人数已经有了答案，但他想考考你的编程能力，因此他想请你帮他用编程算一下最多可以配对多少个人。(本题介绍仅作题目背景使用，无任何其他观点)

输入

每个测试文件仅有一条测试数据。
第一行输入M，N，分别表示男同学的数量，女同学的数量。(1<=M<=100,1<=N<=100)
第二行输入M个正整数，分别表示男同学们的颜值。
第三行输入N个正整数，分别表示女同学们的颜值。
注意，所有人的颜值分数范围在[1,100]

输出

输出最多可以配对的总人数。

样例输入?Copy

5 4
10 65 23 67 80
5 15 60 90

样例输出?Copy

4

提示

样例中第一位男同学和第一位女同学配对，第二位男同学和第三位女同学配对。

#include <stdio.h>

struct Node {
    int vi;
    int id;
};

int cmp(const void* a, const void* b) {
    return ((struct Node*)a)->vi - ((struct Node*)b)->vi;
}

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        struct Node a[n], b[m];

        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i].vi);
            a[i].id = i;
        }

        for (int i = 0; i < m; i++) {
            scanf("%d", &b[i].vi);
            b[i].id = i;
        }

        qsort(a, n, sizeof(struct Node), cmp);
        qsort(b, m, sizeof(struct Node), cmp);

        int count = 0;
        for (int i = 0; i < n; i++) {
            int j = 0;
            while (j < m) {
                if (a[i].vi - b[j].vi <= 5 && a[i].vi - b[j].vi >= -5 && a[i].id != -1 && b[j].id != -1) {
                    ++count;
                    a[i].id = -1;
                    b[j].id = -1;
                    break;
                }
                ++j;
            }
        }

        printf("%d\n", count * 2);
    }

    return 0;
}

马的遍历问题

题目描述

在5*4的棋盘中，马只能走斜“日”字。马从位置(x, y)处出发，把棋盘的每一格都走一次，且只走一次，请找出所有路径。

输入

x,y，表示马的初始位置。

输出

将每一格都走一次的路径总数，如果不存在该路径则输出“No solution!”。

样例输入?Copy

1 1
2 2

样例输出?Copy

32
No solution!

def P(x,y,dep,fx,fy):
    global count
    for i in range(0, 8):
        xx = x+fx[i]
        yy = y+fy[i]
        if xx > 0 and xx < 6 and yy > 0 and yy < 5 and a[xx][yy] == 0:
            a[xx][yy] = dep
            if dep == 20:
                count += 1
            else:
                P(xx, yy, dep+1, fx, fy)
            a[xx][yy] = 0
            
while True:
    x, y = map(int, input().split())
    count = 0
    fx = [1,2,2,1,-1,-2,-2,-1]
    fy = [2,1,-1,-2,-2,-1,1,2]
    a = [[0 for j in range(5)]for i in range(6)]
    a[x][y] = 1
    P(x, y, 2, fx, fy)
    if count == 0:
        print("No solution!")
    else:
        print(count)

图的m着色问题

题目描述

?给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色，请输出着色方案。

输入

输入第一行包含n，m，k分别代表n个结点，m条边，k种颜色，接下来m行每行有2个数u，v表示u和v之间有一条无向边,可能出现自环边，所以请忽略自环边。

输出

输出所有不同的着色方案，且按照字典序从小到大输出方案。

样例输入?Copy

3 3 3
1 2
1 3
2 3

样例输出?Copy

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

def paint(b):
    print(b[0], end=" ")
    for j in range(1, n):
        print(str(b[j]), end=" ")
    print()

def solve(i, n, k, a, b):
    if i < n:
        for j in range(1, k+1):
            flag = 0
            for q in range(n):
                if a[i][q] == 1 and b[q] == j:
                    flag = 1
            if flag == 0:
                b[i] = j
                solve(i+1, n, k, a, b)
            b[i] = 0
    else:
        paint(b)

while True:
    n, m, k = map(int, input().split())
    a = [[0 for j in range(n)] for i in range(n)]
    b = [0 for i in range(n)]
    for i in range(m):
        u, v = map(int, input().split())
        a[u-1][v-1] = 1
        a[v-1][u-1] = 1
    solve(0, n, k, a, b)

素数环

<span style="background-color:#ffffff"><span style="color:#333333"><span style="color:#333333"><span style="background-color:#f5f5f5">6</span></span></span></span>

<span style="background-color:#ffffff"><span style="color:#333333"><span style="color:#333333"><span style="background-color:#f5f5f5">1 4 3 2 5 6
1 6 5 2 3 4</span></span></span></span>

def paint(a):
    for j in range(n):
        print(a[j], end=" ")
    print()

def s(i, n, a, b):
    if i < n:
        for j in range(1, n+1):
            if b[j-1] == 0:
                if i != n-1:
                    flag = 0
                    for k in range(2, a[i-1]+j):
                        if (a[i-1]+j) % k == 0:
                            flag = 1
                            break
                    if flag == 0:
                        a[i] = j
                        b[j-1] = 1
                        s(i+1, n, a, b)
                    a[i] = 0
                    b[j-1] = 0
                else:
                    flag = 0
                    for k in range(2, a[i-1]+j):
                        if (a[i-1]+j) % k == 0:
                            flag = 1
                            break
                    for k in range(2, a[0]+j):
                        if (a[0]+j) % k == 0:
                            flag = 1
                            break
                    if flag == 0:
                        a[i] = j
                        b[j-1] = 1
                        s(i+1, n, a, b)
                    a[i] = 0
                    b[j-1] = 0
    else:
        paint(a)

while True:
    n = int(input())
    a = [0] * n
    b = [0] * n
    a[0] = 1
    b[0] = 1
    s(1, n, a, b)

?