郑州大学算法设计与分析实验2

2024-01-05 23:52
文章标签 算法 分析 设计 实验 郑州大学

本文主要是介绍郑州大学算法设计与分析实验2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断题
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

1

#include<bits/stdc++.h> using namespace std;const int N = 50;
int f[N], n;int main()
{
//	freopen("1.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;f[1] = 1; f[2] = 1;for(int i = 3; i <= n; ++ i)f[i] = f[i - 1]  + f[i - 2];cout << f[n];
}

2

#include<bits/stdc++.h> using namespace std;const int N = 10000010;
int f[N], n;int main()
{
//	freopen("1.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;f[1] = 1; f[2] = 1;for(int i = 3; i <= n; ++ i)f[i] = (f[i - 1]  + f[i - 2]) % 998244353;cout << f[n];
}

3

#include<bits/stdc++.h> 
#define LL long long
using namespace std;const LL mod = 998244353;
LL n;
LL f[3] = {0, 1, 1};
LL a[3][3] = {{0, 0, 0}, {1, 0, 1}, {0, 1, 1}};
void mulself(LL a[3][3])
{LL c[3][3] = {0};for(int i = 0; i < 3; ++ i)for(int j = 0; j < 3; ++ j)for(int k = 0; k < 3; ++ k)c[i][j] = (c[i][j] + (LL) a[i][k] * a[k][j]) % mod;memcpy(a, c, sizeof c);
}void mul(LL f[3], LL a[3][3])
{LL c[3] = {0};for(int i = 0; i < 3; ++ i)for(int j = 0; j < 3; ++ j)c[i] = (c[i] + (LL) f[j] * a[j][i]) % mod;memcpy(f, c, sizeof c);		
}int main()
{// freopen("2.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;while(n){if(n & 1) mul(f, a);mulself(a);n /= 2;}cout << f[0] << endl;
}

4

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;const int N = 1e4 + 10;
char a[N][N];
int n;void solve(int n, int x, int y)
{if(n == 1){a[x][y] = 'X';return;}int m = pow(3, n - 2);solve(n - 1, x, y);solve(n - 1, x, y + 2 * m);solve(n - 1, x + m, y + m);solve(n - 1, x + 2 * m, y);solve(n - 1, x + 2 * m, y + 2 * m);
}int main()
{
//	freopen("2.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin >> n){if(n == -1)	break;int q = pow(3, n - 1);for(int i = 0; i < q; ++ i){for(int j = 0; j < q; ++ j)a[i][j] = ' ';a[i][q] = '\0';}solve(n, 0, 0);for(int i = 0; i < q; ++ i)cout << a[i] << endl;cout << '-' << endl;}return 0; 	
}

5

#include<bits/stdc++.h> 
#define LL long long
using namespace std;const int N = 100010;
int n, L;
double a[N], b[N], s[N];bool check(double mid)
{for(int i = 1; i <= n; ++ i){b[i] = a[i] - mid;s[i] = s[i - 1] + b[i];}double minn = 1e9;for(int i = L; i <= n; ++ i){minn = min(minn, s[i - L]);if(s[i] - minn >= 0)	return true;}return false;
}void solve()
{cin >> n >> L;for(int i = 1; i <= n; ++ i)	cin >> a[i];double l = 0, r = 1e9;while(r - l >= 1e-5){double mid = (l + r) / 2;if(check(mid))	l = mid;else r = mid;	} cout << (int)(r * 1000);
}int main()
{
//	freopen("2.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}

6

#include<bits/stdc++.h> 
#define LL long long
using namespace std;int n, k;
map<int, int>cnt;
void solve()
{cin >> n;for(int i = 1; i <= n; ++ i){int id;	cin >> id;cnt[id] ++;}cin >> k;while(k --){int id; cin >> id;if(cnt.find(id) == cnt.end())	puts("No");else puts("Yes");}
}int main()
{
//	freopen("2.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();
}

7

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N = 1e4 + 10;
LL n, x[N], y[N], ans;
int main()
{
//	freopen("2.in", "r", stdin);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for(int i = 0; i < n; ++ i)	cin >> x[i] >> y[i];sort(x, x + n);sort(y, y + n);for(int i = 0; i < n; ++ i)x[i] -= (i + 1);sort(x, x + n);int mid_x = x[n / 2], mid_y = y[n / 2];for(int i = 0; i < n; ++ i)ans += abs(x[i] - mid_x),ans += abs(y[i] - mid_y);	cout << ans << endl;return 0; 	
}

8

#include <bits/stdc++.h> 
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(register int i = (a); i >= (b); --i)
#define ls p<<1
#define rs p<<1|1
#define PII pair<int, int>
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f 
#define x first
#define y second
using namespace std;
const int N = 1e4 + 10;
int n, x, a[N];
int main()
{IOScin>>n;for(int i = 0; i < n; i ++)cin >> x >> a[i];sort(a,a+n);int min=0;for(int i=0; i<n; i++)min += (int)fabs(a[i]-a[n/2]);cout<<min<<endl;return 0;
}

9

#include <bits/stdc++.h>
#define LL long longusing namespace std;
const int N = 1e6 + 10, INF = 1 << 30;
struct wy
{double x, y;
}p[N];
int n, tmp[N], pos1, pos2;
double ass;double dis(wy a, wy b)
{double x =  (a.x - b.x) * (a.x - b.x);double y =  (a.y - b.y) * (a.y - b.y);return sqrt(x + y);
}bool cmp1(wy a, wy b)
{if(a.x == b.x)	return a.y < b.y;return a.x < b.x; 
}bool cmp2(int a, int b)
{return p[a].y < p[b].y;
}double solve(int l, int r)
{if(l == r)	return INF;int mid = (l + r) >> 1;double d = INF;d = min(solve(l, mid), solve(mid + 1, r));int k = 0;for(int i = l; i <= r; ++ i)if(fabs(p[mid].x - p[i].x) < d)tmp[++ k] = i;sort(tmp + 1, tmp + 1 + k, cmp2);for(int i = 1; i <= k; ++ i)for(int j = i + 1; j <= k && p[tmp[j]].y - p[tmp[i]].y < d; ++ j){double new_d = dis(p[tmp[i]], p[tmp[j]]);d=min(new_d,d);if(d<ass){ass=d;pos1 = tmp[i];pos2 = tmp[j];}}		return d;
}int main()
{
// 	freopen("1.in", "r", stdin);scanf("%d", &n);for(int i = 1; i <= n; ++ i)	scanf("%lf%lf", &p[i].x, &p[i].y);sort(p + 1, p + 1 + n, cmp1);ass=1e18;double ans = solve(1, n);if(p[pos1].x + p[pos1].y > p[pos2].x + p[pos2].y)	swap(pos1, pos2);printf("(%.2f,%.2f),(%.2f,%.2f),miniDist=%.3f", p[pos1].x, p[pos1].y, p[pos2].x, p[pos2].y, ans);return 0;
}

这篇关于郑州大学算法设计与分析实验2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/574560。

相关文章

基于C++的UDP网络通信系统设计与实现详解

基于C++的UDP网络通信系统设计与实现详解

《基于C++的UDP网络通信系统设计与实现详解》在网络编程领域,UDP作为一种无连接的传输层协议,以其高效、低延迟的特性在实时性要求高的应用场景中占据重要地位,下面我们就来看看如何从零开始构建一个完整... 目录前言一、UDP服务器UdpServer.hpp1.1 基本框架设计1.2 初始化函数Init详解
阅读更多...
Springboot请求和响应相关注解及使用场景分析

Springboot请求和响应相关注解及使用场景分析

《Springboot请求和响应相关注解及使用场景分析》本文介绍了SpringBoot中用于处理HTTP请求和构建HTTP响应的常用注解,包括@RequestMapping、@RequestParam... 目录1. 请求处理注解@RequestMapping@GetMapping, @PostMappin
阅读更多...
Spring Boot Interceptor的原理、配置、顺序控制及与Filter的关键区别对比分析

Spring Boot Interceptor的原理、配置、顺序控制及与Filter的关键区别对比分析

《SpringBootInterceptor的原理、配置、顺序控制及与Filter的关键区别对比分析》本文主要介绍了SpringBoot中的拦截器（Interceptor）及其与过滤器（Filt... 目录前言一、核心功能二、拦截器的实现2.1 定义自定义拦截器2.2 注册拦截器三、多拦截器的执行顺序四、过
阅读更多...
Springboot3统一返回类设计全过程(从问题到实现)

Springboot3统一返回类设计全过程(从问题到实现)

《Springboot3统一返回类设计全过程(从问题到实现)》文章介绍了如何在SpringBoot3中设计一个统一返回类,以实现前后端接口返回格式的一致性,该类包含状态码、描述信息、业务数据和时间戳,... 目录Spring Boot 3 统一返回类设计：从问题到实现一、核心需求：统一返回类要解决什么问题？
阅读更多...
C++ scoped_ptr 和 unique_ptr对比分析

C++ scoped_ptr 和 unique_ptr对比分析

《C++scoped_ptr和unique_ptr对比分析》本文介绍了C++中的`scoped_ptr`和`unique_ptr`,详细比较了它们的特性、使用场景以及现代C++推荐的使用`uni... 目录1. scoped_ptr基本特性主要特点2. unique_ptr基本用法3. 主要区别对比4. u
阅读更多...
Nginx内置变量应用场景分析

Nginx内置变量应用场景分析

《Nginx内置变量应用场景分析》Nginx内置变量速查表,涵盖请求URI、客户端信息、服务器信息、文件路径、响应与性能等类别,这篇文章给大家介绍Nginx内置变量应用场景分析,感兴趣的朋友跟随小编一... 目录1. Nginx 内置变量速查表2. 核心变量详解与应用场景3. 实际应用举例4. 注意事项Ng
阅读更多...
Java多种文件复制方式以及效率对比分析

Java多种文件复制方式以及效率对比分析

《Java多种文件复制方式以及效率对比分析》本文总结了Java复制文件的多种方式,包括传统的字节流、字符流、NIO系列、第三方包中的FileUtils等,并提供了不同方式的效率比较,同时,还介绍了遍历... 目录1 背景2 概述3 遍历3.1listFiles()3.2list()3.3org.codeha
阅读更多...
Nginx分布式部署流程分析

Nginx分布式部署流程分析

《Nginx分布式部署流程分析》文章介绍Nginx在分布式部署中的反向代理和负载均衡作用,用于分发请求、减轻服务器压力及解决session共享问题,涵盖配置方法、策略及Java项目应用,并提及分布式事... 目录分布式部署NginxJava中的代理代理分为正向代理和反向代理正向代理反向代理Nginx应用场景
阅读更多...
深入理解Mysql OnlineDDL的算法

深入理解Mysql OnlineDDL的算法

《深入理解MysqlOnlineDDL的算法》本文主要介绍了讲解MysqlOnlineDDL的算法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小... 目录一、Online DDL 是什么？二、Online DDL 的三种主要算法2.1COPY（复制法）
阅读更多...
Redis中的有序集合zset从使用到原理分析

Redis中的有序集合zset从使用到原理分析

《Redis中的有序集合zset从使用到原理分析》Redis有序集合(zset)是字符串与分值的有序映射,通过跳跃表和哈希表结合实现高效有序性管理,适用于排行榜、延迟队列等场景,其时间复杂度低,内存占... 目录开篇：排行榜背后的秘密一、zset的基本使用1.1 常用命令1.2 Java客户端示例二、zse
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2