当前位置: 首页 > article >正文

GXUOJ-算法-第一次作业

1.整数划分

问题描述

GXUOJ | 整数划分

题解

#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;

int n;
int f[N];

int main(){
	cin>>n;
	f[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			f[j]=(f[j]+f[j-i])%mod;
		}
	}
	cout<<f[n];
}

2.汉诺塔

问题描述

GXUOJ | 汉诺塔

题解

#include<bits/stdc++.h>
using namespace std;
int n;

void hnt(int n,char A,char B,char C){
	
	if(n==1) cout<<"Move disk "<<n<<" from "<<A<<" to "<<C<<endl;
	else{
		hnt(n-1,A,C,B);
		cout<<"Move disk "<<n<<" from "<<A<<" to "<<C<<endl;
		hnt(n-1,B,A,C);
	}	
}

int main(){
	cin>>n;
	hnt(n,'A','B','C');
	return 0;
}

3.算法训练 排列问题

问题描述

GXUOJ | 算法训练 排列问题

题解

#include <bits/stdc++.h>
using namespace std;

// 定义全局变量n表示排列的元素个数,k表示要找的第k个排列
int n, k;
// 二维数组table用于存储限制条件,table[i][j]表示j - 1能否出现在i - 1后面
// 1标识 j-1可以出现在 i-1后面  0 标识不能
// 并保证第i行第i列为0
int table[20][20];
// 数组l用于存储当前生成的排列
int l[20];
// sum用于记录满足条件的排列的数量
int sum = 0;

int main() {
    // 输入排列元素个数n和要找的第k个排列
    cin >> n >> k;

    // 读取限制条件表
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // 输入table[i][j]的值,0表示不能,1表示能
            cin >> table[i][j];
        }
    }

    // 初始化排列为0到n - 1
    for (int i = 0; i < n; ++i) {
        l[i] = i;
    }

    // 使用do - while循环生成全排列并检查是否满足条件
    do {
        // flag用于标记当前排列是否满足限制条件
        bool flag = true;

        // 检查相邻元素是否满足限制条件
        for (int i = 0; i < n - 1; ++i) {
            // 如果当前相邻元素不满足限制条件(table值为0)
            if (!table[l[i]][l[i + 1]]) {
                // 将flag设为false,表示不满足条件
                flag = false;
                // 跳出内层循环,不再继续检查后续相邻元素
                break;
            }
        }

        // 如果当前排列满足限制条件
        if (flag) {
            // 满足条件的排列数量加1
            sum++;
            // 如果找到第k个满足条件的排列
            if (sum == k) {
                // 跳出外层循环
                break;
            }
        }
    } while (next_permutation(l, l + n));	
	//C++标准库中的一个循环结构,用于生成数组l所有元素的全排列 

    // 输出结果
    for (int i = 0; i < n; ++i) {
        // 输出排列中的元素
        cout << l[i];
        // 如果不是最后一个元素,则输出一个空格
        if (i < n - 1) {
            cout << ' ';
        }
    }
    return 0;
}

思路解析
 

  1. 布尔变量 flag 的作用

    • flag 就像是一个 “标记器”,初始化为 true 时,它假设当前生成的排列是满足所有限制条件的。在后续对排列的检查过程中,如果发现任何不符合限制条件的情况,就把 flag 设为 false。这样,当整个检查过程结束后,通过查看 flag 的值,就能知道这个排列是否满足所有限制条件。
  2. for 循环遍历相邻元素对

    • for (int i = 0; i < n - 1; ++i) 这个循环的目的是依次检查排列中每一对相邻的元素。因为要检查相邻元素关系,所以循环到 n - 1 即可,因为 l[n - 1] 没有下一个相邻元素可检查了。
    • 对于每一对相邻元素 (l[i], l[i + 1]),程序会去查看 table[l[i]][l[i + 1]] 的值。这里的 table 数组存储着限制条件,table[l[i]][l[i + 1]] 表示 l[i + 1] 这个数能否出现在 l[i] 这个数后面。
  3. 判断与处理

    • 如果 table[l[i]][l[i + 1]] 为 0,这就表明在给定的限制条件下,l[i + 1] 不允许出现在 l[i] 后面,也就意味着当前排列不满足限制条件。此时,将 flag 设为 false,并使用 break 跳出内层 for 循环。因为只要发现一对不满足条件的相邻元素,就可以确定整个排列不满足条件了,无需再检查后面的相邻元素对。
  4. 实例说明

    • 假设 n = 3,限制条件 table 如下:

      0 1 1
      1 0 0
      0 1 0
      
       

      并且当前生成的排列 l 为 [1, 0, 2]

    • 初始化 flag = true

    • 进入 for 循环:

      • 当 i = 0 时,相邻元素对是 (l[0], l[1]),即 (1, 0)。查看 table[1][0](因为 l[0]=1l[1]=0),table[1][0] = 1,说明 0 可以出现在 1 后面,继续循环。
      • 当 i = 1 时,相邻元素对是 (l[1], l[2]),即 (0, 2)。查看 table[0][2](因为 l[1]=0l[2]=2),table[0][2] = 1,说明 2 可以出现在 0 后面。
    • 由于整个循环过程中没有出现 table[l[i]][l[i + 1]] 为 0 的情况,所以 flag 仍然为 true,这就表示排列 [1, 0, 2] 满足限制条件。

    • 再假设当前生成的排列 l 为 [0, 2, 1]

    • 初始化 flag = true

    • 进入 for 循环:

      • 当 i = 0 时,相邻元素对是 (l[0], l[1]),即 (0, 2)。查看 table[0][2]table[0][2] = 1,继续循环。
      • 当 i = 1 时,相邻元素对是 (l[1], l[2]),即 (2, 1)。查看 table[2][1]table[2][1] = 0,这表明 1 不允许出现在 2 后面,所以将 flag 设为 false 并跳出循环。此时就确定排列 [0, 2, 1] 不满足限制条件。

通过这种方式,程序可以逐个检查生成的排列是否符合给定的限制条件。

4.数塔问题

问题描述

GXUOJ | 数塔问题

题解

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 101;

int main() {
    int n;
    cin >> n; // 读取数塔层数

    int f[MAX_N][MAX_N]; // 存储数塔的值
    int a[MAX_N][MAX_N]; // 存储到每个点的最大路径和

    // 读取数塔的每一层的数字
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> a[i][j];
        }
    }

    // 初始化最后一层的最大路径和
    for (int i = 0; i < n; i++) {
        f[n - 1][i] = a[n - 1][i];
    }

    // 从下到上计算每一层的最大路径和
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
        }
    }

    // 输出从顶部到底部的最大路径和
    cout << f[0][0] << endl;

    return 0;
}


http://www.kler.cn/a/454419.html

相关文章:

  • memory泄露分析方法(Binder,Window,View篇)
  • 基于SpringBoot的“房产销售平台”的设计与实现(源码+数据库+文档+PPT)
  • 如何增加多行内容到文件
  • 多旋翼无人机理论 | 四旋翼动力学数学模型与Matlab仿真
  • LeetCode 83 :删除排链表中的重复元素
  • 以太网帧结构
  • Mysql数据究竟是如何存储的
  • flink cdc各种数据库 jar下载地址
  • 【Java 学习】详细讲解---包和导包、Scanner类、输入源
  • 32. 线程、进程与协程
  • javaweb 04 springmvc
  • 【从零开始入门unity游戏开发之——C#篇30】C#常用泛型数据结构类——list<T>列表、`List<T>` 和数组 (`T[]`) 的选择
  • BFD综合详细实验配置案例
  • GitLab 服务变更提醒:中国大陆、澳门和香港用户停止提供服务(GitLab 服务停止)
  • vue3使用video-player实现视频播放(可拖动视频窗口、调整大小)
  • HTTP、HTTPS和SOCKS5代理協議
  • WSL2上Ubuntu22.04安装Docker
  • Windows 使用 非安装版MySQL 8
  • Linux网络——TCP的运用
  • QT集成intel RealSense 双目摄像头
  • NLP 中文拼写检测开源-01-基于贝叶斯公式的拼写检查器 CSC
  • Leetcode 394-字符串解码
  • MinIO服务器文件复制(Windows环境Linux环境)
  • LLMs之o3:《Deliberative Alignment: Reasoning Enables Safer Language Models》翻译与解读
  • 基础排序算法
  • 如何使用 Flask 框架创建简单的 Web 应用?