仓颉编程语言-03-程序设计题目01约瑟夫环问题

仓颉编程语言是一款面向全场景智能的新一代编程语言，主打原生智能化、天生全场景、高性能、强安全。主要应用于鸿蒙原生应用及服务应用等场景中，为开发者提供良好的编程体验。

前面的内容中，已经完成了仓颉编程语言的简介，在线与本地使用，现在基于VSCode完成仓颉编程语言的开发与使用。

约瑟夫问题

题目来源
https://www.luogu.com.cn/problem/P1996

题目描述

$n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 $n-1$ 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 $n,m$。

输出格式

输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。

样例 #1

样例输入 #1

10 3

样例输出 #1

3 6 9 2 7 1 8 5 10 4

提示

$1\le m,n\le 100$

通过仓颉语言完成约瑟夫环问题

通过 VSCode 命令面板创建仓颉工程

在 VSCode 中先打开一个文件夹，如pro01文件夹，然后按 F1 或者 Ctrl + Shift + P（mac 上快捷键为 Command + Shift + P） 或view下的command palette打开命令面板，

然后按照以下步骤创建仓颉工程：

第一步：选择创建 Cangjie 工程命令

第二步：选择 Cangjie 后端

第二步：选择 Cangjie 工程模板

第三步：选择工程路径
这里选择的是cjcpro目录，会在cjcpro目录下创建一个仓颉工程，该工程与pro01目录并列

选择工程位置后，输入工程名称为cjpro01

单击回车键，会弹出一个新的窗口，该窗口就是VScode创建的仓颉工程cjpro01.

打开src下的main.cj会查看到仓颉的demo

实现约瑟夫环

package cjpro01

// 约瑟夫环问题
// 参数:
//   n: 总人数
//   m: 每次数到m的人出列
// 返回值:
//   最后剩下的人的编号
func josephus(n: Int64, m: Int64): Int64 {
    // 创建一个数组来表示所有人
    var people =  Array<Int64>(n){i=>i}

    for (i in 1..=n) {
        people[i]=i
    }

    var j: Int64 = 1
    var cnt: Int64 = people.size
    while (cnt > 1){
        for(i in 1..=n){
            if(people[i] == 0){
                continue
            }
            if(j%m == 0){
                cnt--

                people[i] = 0
                j++
            }else{
                j++
            }
        }
       
    }
    for(i in 1..=n){
        if(people[i] != 0){
            // println(people[i])
            return people[i]
        }
    }
    // 返回最后剩下的人的编号
    return people[1]
}

// 主函数
main(): Int64 {
    // 调用约瑟夫环函数
    let result: Int64 = josephus(41, 3)
    // 打印结果
    println("最后剩下的人的编号是: ($result)")
    return 0
}

编译构建

注：VSCode 中可视化方式提供的仓颉功能编译构建能力依赖 cjpm 工具，该工具要求打开的仓颉工程的模块内必须包含规范的 cjpm.toml 文件。若没有该文件仍想执行工程的编译构建，可在终端使用 cjc 命令。

在 VSCode 中提供四种方式来实现 Cangjie 工程的编译构建方式。
具体可以参考官网，连接如下：
https://cangjie-lang.cn/docs?url=%2F0.53.13%2Ftools%2Fsource_zh_cn%2FIDE%2Fuser_manual.html

我们仅演示2种。

在命令面板执行命令

打开命令面板，通过分类词"Cangjie"来快速找到如下编译相关命令：
Build With Verbose 编译并展示编译日志
输出如下

点击运行按钮运行工程

用户可以点击 cj 文件编辑区的运行按钮来运行整个仓颉工程

若整个工程中配置的output-type为executable时会在终端面板打印运行结果，否则只会显示编译的结果。

点击运行按钮执行的编译过程是结合当前的 cjpm.toml 和 cjpm_build_args.json 的配置来进行的

C++实现约瑟夫环问题

链表版本

#include <stdio.h>
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    struct List
    {
        int num;
        struct List *next;
    };
    List *head = new List;//虚拟头结点
    List *p = new List;//链表结点
    p = head;//初始结点在虚拟头结点位置
    // 创建链表
    for (int i = 1; i <= n; i++)
    {
        List *node = new List;//新建结点
        node->num = i;//赋初值
        node->next = NULL;//新结点的后结点初始化为空
        //p随node移动形成链式结构
        p->next = node;
        p = p->next;
    }
    p->next = head->next;//尾结点指向头结点形成循环链表
    // 遇到m-1 指针跳两个 指向自己时停
    p = head->next;//p从第一个结点开始
    int i = 1;//报数的值
    while (p->next->num != p->num)//只剩一个结点（指针指向自己）时结束
    {
        if (i == m - 1)//出局结点的前一个结点
        {
            printf("%d ", p->next->num);//输出出局者编号
            List *temp = p->next;//临时变量存出局者结点
            p->next = p->next->next;//淘汰出局者
            i = 0;//报数归零
            delete temp;//释放出局者空间
        }
        i++;//从一报数
        p = p->next;//移动链表
    }
    printf("%d", p->num);//输出幸存者编号
    return 0;
}

队列版本

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
queue<int> a;
int main()
{
	int b,c,d,e=1,f=0;
	cin>>b>>c;
	for(int i=1;i<=b;i++)
	{
		a.push(i);//模拟队列 
	}
	while(!a.empty())
	{
		if(e==c)//如果这个人正好被踢 
		{
			cout<<a.front()<<" ";//先输出 
			a.pop();//再删除 
			e=1;//再从1开始报数 
		}
		else if(e!=c)//如果不被剔除 
		{
			e++;//报的数+1 
			a.push(a.front());//先把head压进队尾 
			a.pop();//再把head删除 
		}
	}
	return 0;//结束程序（完美） 
}

总结

到此完成了仓颉语言的VScode插件使用与开发，我会持续更新。
仓颉编程语言作为一个新出现的语言，对其抱有很大的希望，但一个语言的发展也需要很多年的完善，一路同行，共同进步。

仓颉官方链接