1.击鼓传花,初始有n个人围成一个圈,花位于第0个人手上,持花人每秒必须向其右边传花,之后每过s秒,手中持花的人退出比赛之后花传给下一个人,求最后剩下的那个人为几号
2.假设斐波那契列数有1000000项,请设计一个时间复杂度不超过O(n)每次请求时间复杂度为O(1)的算法
1.
#include<stdio.h>
int main()
{
int a[1000],n,s,i,t,cnt=0;
scanf("%d %d",&n,&s);
t=n; //用人数控制循环结束时机
for(i=0;i<s;i++)
a[i]=i;
for(i=0;i<n;i++)
{
if(a[i]!=0) //只计数每个退出圈子的人
cnt++;
if(cnt==s)
{
a[i]=0; //退出圈子的人,标记为0
cnt=0; //cnt清零,重新计数
t--; //每退出一个,总人数就减少一个
}
if(i==n)
i=0; //围成一圈---循环
if(t==1) //只剩一个人的时候,退出循环
break;
}
for(i=0;i<n;i++)
{
if(a[i]!=0)
printf("%d ",a[i]);
}
return 0;
}
1.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAXN 100
void CountOff(int n, int m, int out[]);
int main()
{
int i, n, s, out[MAXN]={0};
scanf("%d %d", &n, &s); //n是总人数,s是间隔秒数
CountOff(n, s, out);
for (i = 0; i < n; i++)
{
if (out[i] == 0)
printf("%d", i + 1); //编号从1开始
}
return 0;
}
void CountOff(int n, int m, int a[])
{
int i, t = n, k = 0;//t表示剩余人数
for (i = 0; i < n; i++)
a[i] = 0;
while (t != 1)
{
for (i = 0; i < n; i++)
{
if (a[i] == 0)
{
k++;
if (k % m == 0)
{
k = 0;
a[i] = 1; //退出的状态置为1
t--; //人数-1
}
}
}
//显示过程
/*for(int k=0;k<n;k++)
printf("%d ",a[k]);
printf("\n");*/
}
}
2.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main()
{
int i = 3;
int a = 1, b = 1;
for (; i <= 1000000; i++) //时间复杂度O(n)
{
if (i % 2 == 0)
{
b = a + b;
//printf("%d ", b);
}
else
{
a = a + b; //每次处理时间复杂度为O(1)
//printf("%d ", a);
}
}
printf("%d", b); //最终结果
return 0;
}
您好,我是有问必答小助手,您的问题已经有小伙伴帮您解答,感谢您对有问必答的支持与关注!