2 xiaohao0033 xiaohao0033 于 2015.05.25 18:26 提问

c语言的一道小问题。。。谢谢

“3”是聚会时大家非常喜欢玩的一款游戏。现在定义游戏规则如下:

n个人围成一圈,序号分别为1-n,从1号玩家从1开始报数。

如果有玩家报的数是3的倍数或者个位数字为3的玩家退出游戏,下一位玩家继续之前的玩家报数,直到场上只剩下1名玩家,这名玩家就是游戏的胜利者。

比如有10个玩家时,对应的游戏过程如下:

所以最后是5号玩家胜利。

现在给出玩家个数n,请输出最终胜利的玩家序号。

输入格式
仅1行,表示参与游戏的玩家个数。

测试用例中,n小于等于65535大于等于1。

输出格式
输出胜利的玩家序号。

#include
int fac3(int n)
{
int a[65535][65535]={0},i,k;
static int l=0;
k=0;
for(i=0;i<n;i++)
{a[l][i]=l*n+i+1;}
for(i=0;i<n;i++)
{
if(a[l][i]!=0||a[l][i]-10*i!=3)
{
a[l+1][k]=a[l][i];
k++;
}
}
l++;

fac3(k);
if(k==1)
{
    for(i=0;i<n;i++)
    if(a[l-1][0]==a[0][i])
    return i;
}

}
int main()
{
int n,m;
scanf("%d",&n);
m=fac3(n);
printf("%d",m);

}

为什么一运行就崩溃啊?希望有好心人帮改一下,谢谢。。。(预处理指令粘贴不上麻烦加一下)

12个回答

caozhy
caozhy   Ds   Rxr 2015.05.25 18:46

a[65535][65535]
这会开一个4GB大小的数组,你的计算机根本分配不了这么多内存。
这就是一个约瑟夫环问题,自己google下看看别人怎么写的。

91program
91program   Ds   Rxr 2015.05.25 19:53

因为不支持这么大的 Stack,可以考虑使用 malloc 来分析空间

91program
91program VS 默认的 Stack 大小是 65536,程序使用的大小就不能大于它,否则开始运行时就报错。
2 年多之前 回复
hanST123
hanST123   2015.05.25 22:04

给你提供一个思路,把int a[65535][65535]={0}放到main()函数的外面作为全局变量放到静态存储区,那么就可以申请到很大的内存了。因为你要是
把它作为局部变量放到堆栈中势必会导致溢出问题。作为全局变量就可以编译通过了。

u012377333
u012377333   Rxr 2015.05.25 19:00

上面的哥们写得对,没必要分配那么大的静态区间。

a1193561652
a1193561652   Rxr 2015.05.25 20:38

楼上说的对,数组太大了,栈段根本不够用。

hanST123
hanST123   2015.05.25 22:04

给你提供一个思路,把int a[65535][65535]={0}放到main()函数的外面作为全局变量放到静态存储区,那么就可以申请到很大的内存了。因为你要是
把它作为局部变量放到堆栈中势必会导致溢出问题。作为全局变量就可以编译通过了。

a24862
a24862   2015.05.25 22:21

没必要开二维数组……这是算把比赛的题目?用最笨的办法如下所示……

 #include <stdio.h>

int main()
{
    int n, a[70000], i, m, num = 1, flag = 0;
    scanf("%d", &n);
    m = n;
    while(1)
    {
        for(i = 0; i < n; i++)
        {
            if(a[i] != -1)
            {
                a[i] = num++;
                if(a[i] % 3 == 0 || a[i] % 10 == 3)
                {
                    a[i] = -1;
                    m--;
                    if(m == 1)
                    {
                        flag = 1;
                        break;
                    }
                }
            }
        }
        if(flag)
            break;
    }
    for(i = 0; i < n; i++)
        if(a[i] != -1)
            printf("%d\n", i + 1);
    return 0;
}
xiaohao0033
xiaohao0033 这个oj上有一个测试说时间超限。怎么破??
2 年多之前 回复
tianyang2008
tianyang2008   2015.05.26 13:57

写代码有点理想了。。

zmp1123
zmp1123   2015.05.26 22:34

可以参见博文C语言经典编程之数组(围圈报数)

#include

int main(void)
{
int m = 0;//人数
int n = 0;//报数
int a[10] = {};
int i = 0, j = 0, k = 0;//k表示目前出圈的人数
// printf("input:");
scanf("%d %d", &m, &n);
// printf("input:");
for(i = 1; i <= m; i++)
{

a[i] = 1;
}

i = 1;
while(1)
{   
    if(a[i] == 1)
    {   
        j++;
    }   
    if(j == n)
    {   
        a[i] = 0;
        j = 0;
        k++;
    }   
    if(k == m - 1)
        break;

    i++;

    if(i > m)
    {
        i = 1;
    }
}

// printf("output:\n");

for(i = 1; i <= m; i++)
{
    if(a[i] == 1)
        printf("%d\n", i);
}

return 0;

}

lzp_lrp
lzp_lrp   Ds   Rxr 2015.05.27 17:16

int a[65535][65535],这个数组太大了吧 65535 * 65535 = 4294836225 ,如果 int占2个byte的话,这需要8G的内存,算法不合理

共12条数据 1 尾页
Csdn user default icon
上传中...
上传图片
插入图片