首页 > 编程语言 >HNUCM-2024年春季学期《算法分析与设计》练习15

HNUCM-2024年春季学期《算法分析与设计》练习15

时间:2024-06-16 21:31:59浏览次数:26  
标签:输出 15 int 样例 2024 n1 HNUCM Copy 输入

问题 A: 简单递归求和

题目描述

使用递归编写一个程序求如下表达式前n项的计算结果:  (n<=100)
1 -  3 + 5 - 7 + 9 - 11 +......
输入n,输出表达式的计算结果。

输入

多组输入,每组输入一个n,n<=100。

输出

输出表达式的计算结果。

样例输入 Copy

1

2

样例输出 Copy

1

-2

import sys
sys.setrecursionlimit(100000)
def f1(n1:int):
    if n1==1:
        return 1
    if n1%2==0:
        return f1(n1-1)-2*n1+1
    else:
        return f1(n1-1)+2*n1-1
while True:
    n1=int(input())
    print(f1(n1))

问题 B: 文件存储

题目描述

如果有n个文件{F1,F2,F3,…,Fn}需要存放在大小为M的U盘中,文件i的大小为Si,1<=i<=n。请设计一个算法来提供一个存储方案,使得U盘中存储的文件数量最多。

输入

多组输入,对于每组测试数据,每1行的第1个数字表示U盘的容量M(以MB为单位,不超过256*1000MB),第2个数字表示待存储的文件个数n。
第2行表示待存储的n个文件的大小(以MB为单位)。

输出

输出最多可以存放的文件个数。  

样例输入 Copy

10000 5

2000 1000 5000 3000 4000

样例输出 Copy

4

while True:
    m1,n1=map(int,input().split())
    a1=list(map(int,input().split()))
    a1.sort()
    ans=0
    for i in range(n1):
        if a1[i]<=m1:
            ans+=1
            m1-=a1[i]
    print(ans)

 问题 C: 图的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 config(x: int, y: int):
    for i in range(1, x):
        if maze[i][x] == 1 and path[i - 1] == y:
            return True
    return False
 
 
def draw(x: int):
    if x > n:
        paths.append(path[:])
        return
    else:
        for i in range(1, k + 1):
            if not config(x, i):
                path.append(i)
                draw(x + 1)
                path.pop()
        return
 
 
while True:
    try:
        n, m, k = map(int, input().split())
        maze, paths, path = [[0] * (n + 1) for _ in range(n + 1)], [], []
        for _ in range(m):
            a12, b1 = map(int, input().split())
            if a12 != b1:
                maze[a12][b1] = maze[b1][a12] = 1
        draw(1)
        paths.sort()
        for path in paths:
            for j1 in range(len(path)):
                print(path[j1], end='') if j1 == 0 else print('', path[j1], end='')
            print()
    except:
        break

 问题 D: N皇后问题

题目描述

使用回溯法求解N后问题。

输入

皇后的个数。

输出

每一种方案及总方案数。

样例输入 Copy

4

样例输出 Copy

   0 1 0 0

   0 0 0 2

   3 0 0 0

   0 0 4 0

----------------

   0 0 1 0

   2 0 0 0

   0 0 0 3

   0 4 0 0

----------------

总方案数为:2

def solve(i):
    global n1,count
    for j in range(n1):
        if m[j]==0 and l[i+j]==0 and r[i-j+n1]==0:
            a[i][j]=i+1
            m[j]=l[i+j]=r[i-j+n1]=1
            if i==n1-1:
                p(a)
                count+=1
            else:
                solve(i+1)
            a[i][j]=0
            m[j]=l[i+j]=r[i-j+n1]=0
    return count
def p(a):
    for i in range(n1):
        for j in range(n1):
            print(a[i][j],end=' ')
        print()
    print("----------------")
n1=int(input())
count=0
a=[[0]*n1 for _ in range(n1)]
m=[0]*n1
l=[0]*(2*n1)
r=[0]*(2*n1)
k=solve(0)
print("总方案数为:"+str(k))

 问题 E: 马的遍历问题

题目描述

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

输入

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

输出

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

样例输入 Copy

1 1

2 2

样例输出 Copy

32

No solution!

def check(x,y):
    if x>=1 and x<=5 and y>=1 and y<=4 and a[x][y]==0:
        return True
    else:
        return False
def slove(x,y,step):
    global number
    fx1=[1,2,2,1,-1,-2,-2,-1]
    fy1=[2,1,-1,-2,-2,-1,1,2]
    for i in range(8):
        nextx=x+fx1[i]
        nexty=y+fy1[i]
        if check(nextx,nexty)==True:
            a[x][y]=step
            if step==20:
                number+=1
            else:
                slove(nextx,nexty,step+1)
            a[x][y]=0
while True:
    x,y=map(int,input().split())
    number=0
    a=[[0 for j in range(5)]for i in range(6)]
    a[x][y]=1
    slove(x,y,2)
    if number==0:
        print("No solution!")
    else:
        print(number)

问题 F: 素数环

题目描述

现有1,2,3...,n,要求用这些数组成一个环,使得相邻的两个整数之和均为素数,要求你求出这些可能的环。

输入

输入正整数n。

输出

输出时从整数1开始逆时针输出,同一个环只输出一次,且满足条件的环应按照字典序从小到大输出。
注:每一个环都从1开始。

样例输入 Copy

6

样例输出 Copy

1 4 3 2 5 6

1 6 5 2 3 4

def solve(i,n,g1,c):
    if i<n:
        for j in range(1,n+1):
            if c[j-1]==0:
                if i!=n-1:
                    check=0
                    for k in range(2,g1[i-1]+j):
                        if (g1[i-1]+j)%k==0:
                            check=1
                            break
                    if check==0:
                        g1[i]=j
                        c[j-1]=1
                        solve(i+1,n,g1,c)
                    g1[i]=0
                    c[j-1]=0
                else:
                    check=0
                    for k in range(2,g1[i-1]+j):
                        if (g1[i-1]+j)%k==0:
                            check=1
                            break
                    for k in range(2,g1[0]+j):
                        if (g1[0]+j)%k==0:
                            check=1
                            break
                    if check==0:
                        g1[i]=j
                        c[j-1]=1
                        solve(i+1,n,g1,c)
                    g1[i]=0
                    c[j-1]=0
    else:
        for j in range(n):
            print(g1[j],end=" ")
        print()
while True:
    n=int(input())
    g1=[0 for i in range(n)]
    c=[0 for j in range(n)]
    g1[0]=1
    c[0]=1
    solve(1,n,g1,c)

 问题 G: X星人的迷宫

题目描述

X星人进入了一个树形迷宫,该迷宫由一个N层的满二叉树组成。迷宫的每一个节点都有一个计分权重,只有找到那条从根节点开始到叶子结点的计分权重和最大的路径,X星人才能够顺利走出迷宫。
现在给出该树形迷宫每一个节点的权重值,你能否编写一个程序计算出权重和最大的路径所对应的总权重。

输入

单组输入。
第1行输入一个正整数N,表示二叉树的节点层数。(N<=20)
第2行输入2^N-1个正整数,分别表示迷宫中每一个节点的权重,两两之间用英文空格隔开。第1个数字表示根节点的权重,接下来两个数字表示根节点左、右孩子的权重,再接下来四个数字表示第3层的四个节点的权重,......,以此类推。每个节点的权重均不超过1000。

输出

输出从根节点出发到叶子节点权重和最大的路径所对应的权重。

样例输入 Copy

3

10 20 30 100 20 50 40

样例输出 Copy

130

#include<bits/stdc++.h>
using namespace std;
int nums[1048890];
int sum[] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287};
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < (int) pow(2.0, n) - 1; i++)
        cin>>nums[i];
    for(int i = n - 2; i >= 0; i--){
        for(int j = 0; j < (int) pow(2.0, i); j++){
            nums[sum[i] + j] = nums[sum[i] + j] + max(nums[sum[i + 1] + 2 * j], nums[sum[i + 1] + 2 * j + 1]);
        }
    }
    cout << nums[0] << endl;
    return 0;
}

 问题 H: 您好中国

题目描述

小明一天突发奇想,随机生成了一个全部由大写字母组成的方阵。他惊奇地发现这个方阵中包含中国的英文单词“CHINA”。
他希望你能够编写一个程序,能够找出一个由大写字母组成的方阵中所有不同的“CHINA”,要“CHINA”求中五个字母要连续出现,方向可以是上、下、左、右中的任意一个。
例如在下面的4*4的方阵中就包含了两个不同的“CHINA”。一个是第1行第1列到第3列的“CHI”,加上第2行第3列的“N”以及第2行第2列的“A”组成的“CHINA”;还有一个是第1行第1列到第3列的“CHI”,加上第2行第3列的“N”以及第3行第3列的“A”。
CHIA
CANT
GRAC
BBDE

输入

单组输入,每个测试样例包含N+1行。
第1行为方阵的大小N(N<=30)。
第2行到第N+1行用于存储由大写字母组成的方阵,每一行包含N个大写字母。

输出

输出方阵中包含的不同的CHINA的个数。如果一个都没有找到,则输出0。

样例输入 Copy

4

CHIA

CANT

GRAC

BBDE

样例输出 Copy

2

#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<string.h>
#include<queue> 
using namespace std;
int n,cnt;
char c[37][37];
string str="CHINA";
int vis[37][37];
void dfs(int x,int y,int t){
	if(x<0||x>=n||y<0||y>=n)
	return;
	if(t>=5){
		cnt++;
		return ;
	}
	if(c[x+1][y]==str[t]){
		vis[x+1][y]=1;
		dfs(x+1,y,t+1);
		vis[x+1][y]=0;
	}
	
	if(c[x-1][y]==str[t]){
		vis[x-1][y]=1;
		dfs(x-1,y,t+1);
		vis[x-1][y]=0;
	}
	
	if(c[x][y+1]==str[t]){
		vis[x][y+1]=1;
		dfs(x,y+1,t+1);
		vis[x][y+1]=0;
	}
	if(c[x][y-1]==str[t]){
		vis[x][y-1]=1;
		dfs(x,y-1,t+1);
		vis[x][y-1]=0;
	}
}
int main(){
	
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>c[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(c[i][j]=='C'){
				vis[i][j]=1;
				dfs(i,j,1);
				vis[i][j]=0;
			}
		}
	}
	
	cout<<cnt<<endl;
} 

 点赞加关注是您对我的认可,谢谢支持,再次感谢。

标签:输出,15,int,样例,2024,n1,HNUCM,Copy,输入
From: https://blog.csdn.net/2303_76399326/article/details/139689398

相关文章

  • 2024年Java后端开发学习路线(建议收藏!)
    第二部分:Java高级在Java高级中,我们应该要熟练掌握。Java多线程/高并发,数据结构和算法,设计模式和JVM。第三部分:JavaWEB学习JavaWeb也就算正式开始了Java项目的开发,在这个阶段需要掌握Tomcat服务器的搭建,数据的传输。第四部分:主流框架和项目管理在这个阶段,我们需要......
  • [240615] X-CMD 发布 v0.3.11,增加对 elvish 的支持
    目录X-CMD发布v0.3.11,增加对elvish的支持,并优化对nushell,fish,xonsh,tcsh的支持✨co模块-copilot✨elv模块✨hubX-CMD发布v0.3.11,增加对elvish的支持,并优化对nushell,fish,xonsh,tcsh的支持✨co模块-copilot新增功能:现在可以在--co|,子命......
  • SCCPC 2024 游记
    省流:都是uuz的问题比赛前晚5.2h幽默睡眠。9点开考,然后uuz签到失败,byd这都要吃一发罚时。然后开考前1hnit给出了3个假做法,看错了两个题/strongzhicheng稳定发挥,屠杀了剩下的签到和模拟题。期间跟uuz讨论G,发现怎么写都是\(\log^3\)的逆天复杂度,讨论了半个......
  • 2024/6/16 今日随笔
    一、实验目的通过使用JavaMVC模式设计简单的数据库管理系统,巩固使用JDBC技术访问数据库的方法,学习使用Java语言对服务器端进行编程,深入理解MVC网站设计模式的基本概念和框架结构。二、实验内容和基本要求从以下列举的四个数据库中,任选其一,或者自行定义其他数据库,每个数据库中......
  • BUUCTF-Misc(151-160)
    [DDCTF2018]第四扩展FSbinwalk提取一下然后提取出来一个加密压缩包,密码就在图片的备注里Pactera提取出来是一个文本字频统计得到flagflag{huanwe1sik4o!}Beautiful_Side010editor打开,发现一个png文件,我们提取出来发现是半张二维码然后打开QRazyBox-QRCodeAnal......
  • emojiCTF2024
    看到一个新生赛,来打打,发现自己还是太菜了连最正常的hash扩展一开始都没看出来,丢大脸这次就巩固了一下hash扩展密码其他的都是常规题了其他方向基本不会,新生赛都打不了,(哭crypto签到0111001001111010011000100111011101110110010100000100011101010011011110110011000101100......
  • 2024数据库期末综合解析(部分题)
    目录第4关:数据记录修改           任务描述              补充                答案:第6关:数据查询二         任务描述            补充 ......
  • 3.15
    所花时间:4h代码量:430博客量:1了解的知识点:1.Android连接Mysql数据库教程以及增删改查_android访问mysql增删查改源码-CSDN博客更新数据第一步,修改activity_main.xml文件(添加一个更新按钮和输入框)<?xmlversion="1.0"encoding="utf-8"?><LinearLayoutxmlns:android="ht......
  • [转]32th@深入解析C++并发编程:从多线程到现代C++并发库@20240616
    深入解析C++并发编程:从多线程到现代C++并发库你有没有想过,为什么C++在多线程并发编程方面如此强大?C++11标准的发布,为并发编程带来了哪些革命性的变化?本文将深入探讨C++并发编程背后的技术原理,带你领略现代C++并发库的强大之处。文章将结合代码片段,为你揭示C++并发编程的精髓。1.......
  • SCCPC2024 游记
    打了一堆板子,一个都没用上。队友:zhicheng,nityacke开场发现H是签到,NIT签了。然后盯F(圆向某个方向运动,问存不存在一个时刻使得全在长方形之内),发现不外乎一堆二次方程,直接冲。但是zhcheng发现这是巨大蠢题,我的做法是什么极霸东西。这个时候NIT胡了个假B。我去看(给若干\(......