qq_40738424 2019-10-24 12:48 采纳率: 66.7%
浏览 782
已结题

约瑟夫环 - 2 用数组和链表分别该怎么做啊,求求代码思路

约瑟夫问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,执行下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。

问题即,给定人数、起点、方向和要跳过的数字,选择初始圆圈中的位置以避免被处决。

现在有n个人,编号依次为1~n,站成一个圈。从1号开始报数,然后是2号,3号...,每跳过k个人处决一个人。问几号活下来了?

输入描述
输出两个正整数n,k。(1 <= n <= 1000, 1 <= k <= n)
输出描述
输出活下来的人的编号
样例输入
11 5

  • 写回答

3条回答 默认 最新

  • dabocaiqq 2019-10-24 12:53
    关注
    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    
    using namespace std;
    
    typedef struct Node
    {
        int value;
        struct Node* next;
    } Node, *ListNode;    //定义数据节点 和 指针
    
    ListNode createList(int total)
    {/*创建链表*/
        int index = 1;
        Node* pre, * curr;
        ListNode L = new Node;  //第一个节点
        L->next = NULL;
        L->value = index; // 赋值为1
        pre = L;
    
        while(--total > 0)  // 创建后续n-1个节点
        {
            curr = new Node;
            curr->value = ++index;
            pre->next = curr;
            pre = curr;
        }
        curr->next = L; // 首尾相接,使链表成为循环的
        return L;
    }
    
    void run (int total, int tag)
    {/* run函数来进行节点的删除 */
        ListNode L = createList(total); // 创建链表
        ListNode node = L;
        Node* pre = NULL;   // 后继节点
        int index = 1;
        if(tag == 1)
        {
            while (L->next!=NULL) {
              L = L->next;
            }
            printf("最后一个节点为:%d\n",L->value);
            return ;
        }
    
        while(node && node->next)
        {
            if(index == tag)
            {// 删除节点操作
                printf("删除节点:%d\n",node->value );
                pre->next = node->next;
                node->next = NULL;
                node = pre->next;
            }
            else
            {// tag!=1的前提下,刚进入循环 或者 刚执行完删除节点操作时 执行此else
                pre = node; // pre前移
                node = node->next;  // node前移
                index++;  // 计数器自增
            }
        }
    }
    
    int main()
    {
        run(6,3); // run(节点数,要删除的标记数)
        return 0;
    }
    
    评论

报告相同问题?

悬赏问题

  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 Arcgis相交分析无法绘制一个或多个图形