[编程入门]报数问题-题解(C语言代码)

7973 阅读 20 评论 1 点赞

这里用数组和链表两种来解决问题

**数组做法**
```c
#include <stdio.h>
int main()
{
	int n,j,i,current = -1;
	scanf("%d",&n);
	int a[n];
	for(i=1;i<=n;i++)			//将初始的数按1,2,3放入数组中 
		a[i-1] = i;
	while(n!=1)					//当总数为1时说明数组中只剩下一人 
	{
		for(j=1;j<=3;j++)
			current = (current+1)%n;	//current作为报数的下标 
		//printf("\n要删除的数为%d\n",a[current]);
		for(j=current+1;j<n;j++)		//将下标后面的值依次往前移 
			a[j-1] = a[j];
		current--;						//去掉一个数后报数下标也要往前移一次 
		n--;							//总人数减去1 
	}
	printf("%d",a[0]);					//打印最后留在a[0]或者a[current+1]中的数即为最后一人 
 } 
```

**用链表来解决问题，约瑟夫环，实际上就是循环链表**
```c
#include <stdio.h>
#include <stdlib.h>			//报数问题也就是约瑟夫环，用链表或数组都可以 
typedef struct node{		//定义一个结构体，中间存放下一位置的指针以及数据 
	int data;
	struct node *next;
}Node,*List;

List Init_list(int n)		//初始化表，传入的n为所要求的人数 
{
	int i;
	Node *t = (Node *)malloc(sizeof(Node));				 //创建一个指针t，t指针的数据域不赋值，用来作为移动的指针 
	t->next = NULL;										
	List head = t;										//定义一个头节点，存放指针t的地址，为了最后一个节点指向头节点的后一个数据，也就是1的位置 
	for(i=1;i<=n;i++)	
	{
		Node *temp = (Node *)malloc(sizeof(Node));		//创建一个指针temp，放入对应数据 
		temp->data = i;									
		temp->next = NULL;
		t->next = temp;									//将temp插入t指针的指针域中 
		t = temp;										//插完之后t指针应该指向temp的内存地址为了下一次能够继续插入 
	}
	t->next = head->next;								//此时的t作为尾节点，其指针指向1(也就是head->next) 
	return head;
}

/*void display(List head,int n )		//检测是否是循环列表 
{
	int i;
	head = head->next;
	for(i=1;i<=n;i++){
		printf("%d,",head->data);
		head = head->next;
	}
		
}
*/

void find_del(List head,int m,int k)				//找数并且删除，直到最后一个数据 ，head为链表头节点，m为第几个开始，k为报数 
{
	Node *p,*t;										//这里定义两个指针，p指向正在报数的地址，t指向p的前驱节点 
	int i;
	p = head;
	for(i=1;i<=m;i++){								//这里做的是定位到第几个数据开始报 ， 
		t = p;										//每循环一次t指向p，p指向下一个节点 
		p = p->next;
	}
	while(p!=p->next)								//因为是循环链表，当链表中数据只剩下一个时，它对应的指针域应该指向它自己 
	{
		for(i=1;i<k;i++){							//根据k进行移动，因为每一节点的指针域都指向对应节点，就不用像数组一样要考虑最后一个节点指向哪里 
			t = p;
			p = p->next;
		}
		t->next = p->next;							//此时p指向报到k的的地址，t为p的前驱节点，也就是前面一个，这时我们要删除的是p所指的节点，(连接下面，写满了) 
		free(p);								   //那么只需要将指针t的下一节点改为p的下一节点指针域，并且free(p),也就是删除p指针的数据 
		p = t->next;								//这时p指针中为空，那么将p指向t的指针域也就移动到删除数的后面一节点了 
	}
	printf("%d",p->data);							//while出来，即为所剩下来的数据 
	free(p);										
	p = NULL;
 }

int main()
{
	int n;
	scanf("%d",&n);
	List head = (Node *)malloc(sizeof(Node));
	head = Init_list(n);
	//display(head,n);								//可以用来测试是否为循环链表 
	find_del(head,1,3);
	return 0;
}
```

大家给个小星星呀

0.0分

88 人评分

本文分类：题解列表
浏览次数：7973 次浏览
发布日期：2019-12-01 14:50:58
本文链接：https://blog.dotcpp.com/a/63343

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 20 条评论

我要学习摆 2年前回复TA

@追梦人 current后面又不会自增了，不加1你咋搞

我要学习摆 2年前回复TA

大师，我悟了

dotcpp0626434 2年前回复TA

为什么第一个数组的方法可以int a[n],这个n不是变量吗,而且我的devc++还能编译运行????

linmanba 2年前回复TA

@stolen 6

ashinchen5 2年前回复TA

@真的菜菜 这里只是为了方便阅读，创建节点的时候用Node,表的时候用List

皮济 2年前回复TA

@追梦人 因为每次报数都要+1，至于为什么一开始current=-1，是要让一开始从1开始报，而报的1的位置在数组中下标是0

不惧黑夜 2年前回复TA

@真的菜菜 一样吧 我觉得

追梦人 2年前回复TA

current为什么要等于-1，为什么不能直接让它等于0后面current=current%n？

真的菜菜 2年前回复TA

链表这里我有个问题，按照我的理解，Node和*List都是结构体的别名，那么头节点Node *t = (Node *)malloc(sizeof(Node));   是不是等同于List t = (List)malloc(sizeof(Node));   呢

stolen 2年前回复TA

#include<stdio.h>
int main(){
	int a[50];
	int i;
	int allNum=0,restNum=0,count=0,roundcount=0;
	scanf("%d",&allNum);
	for(i=0;i<=allNum;i++){
		a[i] = i + 1; // 1 2 3 put into;
	}
	restNum = allNum; 
	
	while(restNum > 1){
		roundcount = 0;
		//遍历数组;
		while(roundcount < allNum){
			if(a[roundcount]!=0){
				count++;
				//报数报到3 就给标记一下，然后就restNum 减少人数
				if(count==3){
					a[roundcount] = 0; // 退出的人标记为0
					restNum--;
					count=0;
				}
			}
			roundcount++;
		}
	}
	for(i=0;i<allNum;i++){
				if(a[i]!=0){
					printf("%d",a[i]);
					break;//直接结束吧; 输出一个
				}
			}
	return 0;//正常退出程序；
}

[编程入门]报数问题-题解(C语言代码)

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 20 条评论

发表评论 取消回复

评论列表共有 20 条评论

发表评论取消回复