1.定義

給出正整數n，表示一個從1~n的環，再給出一個報數m，開始從1開始報數，報到m時，從環中去掉這個數，下個位置繼續從1開始報數，直到整個環沒有數字為止，依次輸出這些數。

2.思路

解決這種環形問題，我們首先想到的是循環結構體，這里采用循環單鏈表來解決，記錄前驅節點和當前節點位置，當當前節點p的報數等于m時，利用前驅節點刪除它，用一個count計數，當刪除的數為n時，讓當前節點為空，則退出了循環。

這里給出一個n為8的環。

3.代碼實現：

import java.util.Scanner;//定義節點信息 class Node{int data;Node next;public Node(int data){ this.data=data;} } class Solution{//用單循環鏈表來創建約塞夫環public void CreateLink(int n,Node h,Node r){for (int i = 1; i <=n ; i++) {Node p=new Node(i);r.next=p;r=r.next;}r.next=h.next;}//約塞夫環解決方法public int[] way(int n,int m,Node h,Node r){Node p=h.next,pre=r; //p為當前節點,pre為前驅節點int k=0,count=0; //k為當前節點報數，count為刪除節點數int res[]=new int[n]; //用數組來保存結果while (p!=null){ k++; //當前報數if (k==m){ //等于最大報數時，刪除節點res[count++]=p.data;if (count==n){ //退出循環操作p=null;continue;}pre.next=p.next; //刪除節點p=p.next;k=0; //下個節點從新開始計數}else { //不符合條件，后移p=p.next; pre=pre.next;}}return res;} } public class Joseph_circle {public static void main(String args[]){Solution solution=new Solution();Scanner sc=new Scanner(System.in);int n=sc.nextInt(); //節點個數int m=sc.nextInt(); //報數最大值Node h=new Node(0); //帶頭結點的鏈表Node r=h;solution.CreateLink(n,h,r);int res[]=solution.way(n,m,h,r);for (int k:res) {System.out.println(k);}} }

4.實驗結果

輸入n=8，m=3的結果

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的约塞夫环问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。