所以我有以下问题:
下个月将在这座城市举行一次大型会议。通常是朋友
往往会一起到达并注册,所以他们也最终坐在旁边
互相交流,并与他们已经认识的人聊天。在
为了给事情增添趣味,会议组织者想出了办法
一种“洗牌”话务员秩序的系统,从而使他们得到
去与新朋友会面。
该系统的工作方式如下:第一个人到达
会议注册会获得一张随机选择号码a1的门票
由组织者。以下到达的每个人都会得到一个新的
编号为ai =(ai – 1×31334)mod 31337的机票,并找到其
在队列中的相应位置,在最后一个人之后
具有小于或等于ai的数字。这意味着机票号码
队列中的队列应该总是井井有条,如果已经有很多
人数相同的人,最晚到达的应该是最后一个
在那个小组中。
您的任务是编写一个计算机程序,以帮助服务员
找到他们在队列中的正确位置。
示例给定初始票号a1 = 7546,找到位置
在第六个人到达的队列中。所以这里的输入是[7546,
6]。
讨论:第一个到达的人获得票证a1 = 7546并且
站在队列的最前面。第二人获得票证a2
=(7546×31334)mod 31337 = 8699,因此位于队列中的第二个位置。然后到达的第三人获得票
编号为a3 =(8699×31334)mod 31337 = 5240并因此得到
跳过队列并站在位置1,将其他人移入
将队列向后排一个位置。也就是说,队列现在看起来像:
1:5240(3),2:7546(1),3:8699(2)
递增顺序,括号中的数字是中的原始顺序
参加者到达会议。
继续这个顺序,第四,第五和第六位参与者
将获得票证编号a4 = 15617,a5 = 15823和a6 = 15205;所以
队列将如下所示:
1:5240(3),2:7546(1),3:8699(2),4:15205(6),5:15617(4),6:
15823(5),即到达的第六个人站在
队列中的第4位。
答:4
以及以下c ++代码:
#include <iostream>
using namespace std;
int main ()
{
int n, i, poz, ok;
long long int a, v[100], aux;
cout << "v[1]= "; cin >> v[1];
cout << "n= "; cin >> n;
for (i=2; i<=n; i++)
v[i]=(v[i-1]*31334)%31337;
a=v[n];
do
{
ok=0;
for (i=1; i<n; i++)
if (v[i]>v[i+1])
{
aux=v[i];
v[i]=v[i+1];
v[i+1]=aux;
ok=1;
}
}while (ok==1);
for (i=1; i<=n; i++)
if (v[i]==a)
poz=i;
cout << poz;
return 0;
}
它为小数字显示正确的内容,但是当我输入大数字时,就会出现问题,因为它会中断。
例如,对于[7253,10],它显示4;对于[24284,10],它显示1;但是当我输入[12879,505]时,它会中断。
任何想法?
最佳答案
即使不检查您的代码,我也可以说即使对于signed int
,整数溢出也不是问题:31337² = 982,007,569
,即111010100010000011111100010001
,一个30位数字。
因此,此处的计算绝对不能超过(2^31)-1 = 2,147,483,647
的MAX INT。
就像一个琐事一样,long long int
支持的数字最多为(2^63)-1 = 9,223,372,036,854,775,807
。
现在需要做的是调试代码...
根据您的错误-我相信问题是您定义了一个大小为100的arrav v
,并试图找到第505个元素-本质上这是非法的内存访问,因此无法预测。
您正在对自己的代码执行缓冲区溢出:)
除此之外,我建议您花一些时间来组织代码-#define
或为常量添加const
值(数组大小,31337、31334等)
请记住,C ++中的数组以v[0]
开头,而不是以v[1]
开头-不管用文本描述什么。这是个错误。
即使块后面只有一个表达式,也可以用块for
封装if
和{ }
语句-或将来添加代码时,您会忘记它们,并且在调试时会花很多时间。
作为一般建议-避免烦恼,养成使用Yoda大小写的习惯:1 == ok
而不是ok == 1
,因为将错字变成ok = 1
会导致您非常讨厌的错误。