开放性试题文档格式.docx
- 文档编号:4508991
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:21
- 大小:67.61KB
开放性试题文档格式.docx
《开放性试题文档格式.docx》由会员分享,可在线阅读,更多相关《开放性试题文档格式.docx(21页珍藏版)》请在冰点文库上搜索。
i=2(第三天)
2143
3412
4321
表9.1.1
通过上述方法,我们将赛事安排对应一张同余表。
设同余表A,其中
A[i,x]—第i天与x队交锋的球队序号(0≤i≤n-1,1≤x≤n)。
同余表的计算过程如下:
fori←0ton-2do{依次计算每一天的比赛场次}
forx←1tondo {枚举x队的序号}
begin
y←((n-1)+i-x)mod(n-1);
{计算第i+1天与x队交锋的y队序号}
ify=0theny←n-1;
A[i,x]←y;
ifA[i,x]=xthenbeginA[i,x]←n;
A[i,n]←x;
end;
{then}
end;
{for}
在同余表中,同一天里出现了x:
y和y:
x的对垒阵局,它们同属一个场次。
我们不妨取x<
y的一组,使得一天进行
场互不相交的比赛:
fori←0ton-2do
输出第i+1天的比赛提示;
forx←1tondoifx<
A[i,x]then输出x队与A[i,x]队交锋;
如果题意稍作变化:
n可为奇数时怎么办?
显然,为了使每个队与其余队交锋一次,每天让每个队出场一次,比赛天数定为n天,每天设
场次。
我们通过下述方法计算比赛方案:
列模数方程
(x+y)modn=i(1≤i≤n-1)
由此得出
y=(n+i-x)modn
若x球队的序号一旦确定,则按照上式得出与之交锋的y队序号。
由于n为奇数,1≤i≤n-1,因此x≠y。
为了使得模数方程得出的y值对应球队序号,不妨假设y=0时,y确定为n。
fori←0ton-1do
forx←1tondo
y←(i+n-x)modn;
ify=0thenk←n;
a[i,x]←y;
fori←0ton-1do
【例题9.2】cantor表
现代数学的著名证明之一是GeorgCantor证明了有理数是可枚举的。
他是用下面这一张
表来证明这一命题的:
1/11/21/31/41/5...
2/12/22/32/4...
3/13/23/3...
4/14/2...
5/1
我们以z字型给上表的每一项编号。
第1项是1/1,然后是1/2,2/1,3/1,2/2...
整数n(1≤n≤10)
表中的第N项
样例:
input:
n=7
output:
1/4
1.cantor表的特点
cantor表中数据的“走势”如图9.1.1所示:
图9.1.1
元素的特征为
第i条右对角线有i个元素
第奇数条对角线方向向上、第偶数条对角线方向向下;
2.计算第n项的前一行序号l
1+2+…+l<
n≤1+2+…+l+(l+1)
计算过程如下:
l←1;
while
<
ndol←l+1;
l←l-1;
3.计算第n项在第l+1条对角线的位置
(n-
,l+2-n+
)l为奇数
(l+2-n+
,n-
)l为偶数
由此得出算法:
{计算第n项的前一行序号l}
n←n-
-1;
{计算第n项在第l+1条对角线的位置}
ifodd(l)
thenbegin
x←1+n;
y←l+1-n;
end{then}
elsebegin
y←1+n;
x←l+1-n;
{else}
writeln(x,’/’,y);
【例题9.3】最大公约数与最小公倍数问题
输入二个正整数x0,y0(2≤x0<
100000,2≤y0≤1000000),求出满足下列条件的p,q的个数:
条件:
1.p,q是正整数
2.要求p,q以x0为最大公约数,以y0为最小公倍数。
x0,y0
满足条件的所有可能的两个正整数的个数。
输入输出样例:
x0=3y0=60
4
说明:
(不用输出)此时的pq分别为:
360
1512
1215
603
所以满足条件的所有可能的两个正整数的个数共4种。
1.如何判别两个自然数互质
要判别自然数x与y是否互质,必须先计算x和y的最大公约数。
如果两者的最大公约数为1,则表明x与y互质。
设gcd(x,y)为x和y的最大公约数
gcd(x,y)=
functiongcd(x,y:
longint):
longint;
ify=0thengcd←x
elsegcd←gcd(y,xmody);
{gcd}
显然,gcd(x,y)=1是x与y互质的标志。
除1以外的任何自然数n都可以唯一的分解成质数的乘积
n=p1l1*p2l2*…pklk(质数p1<
p2<
…<
pk,质数的次幂l1,l2…,lk>
0)
2.如何计算以x0为最大公约数,以y0为最小公倍数的(p,q)个数
首先,必须明确几个问题
⑴若y0不能整除x0,则不存在以x0为最大公约数、以y0为最小公倍数的(p,q);
⑵若x0=y0,则p=q=x0=y0,即满足条件的p和q仅为一对(x0,y0);
⑶若x0≠y0且y0整除x0,则由于p和q呈自反关系(如果(p,q)以x0为最大公约数、以y0为最小公倍数的话,则(q,p)亦是以x0为最大公约数、以y0为最小公倍数的),因此满足条件的p和q一定为偶数对;
那么,如何求(p,q)的个数呢。
设
=n=1*p1l1*p2l2*…pklk
显然,p0=x0和q0=x0*p1l1*p2l2*…pklk=y0满足条件;
p1=x0*p1l1和q1=x0*p2l2*…pklk满足条件;
p2=x0*p2l2和q2=x0*p1l1*p3l3*…pklk满足条件;
………;
pk=x0*pklk和q2=x0*p1l1*p3l3*…pk-1lk-1亦满足条件。
由于p1l1*的关系自反((p,q)=(q,p)),因此若
分解出k个质数的乘积的话,则满足条件的p和q的个数有
例如x0=4,y0=24
由于
=6=2*3,因此
(4,24)(24,4)
(8,12)(12,8)8=4*212=4*3
满足条件的(p、q)有4对。
又如x0=4,y0=420
由于
=105=3*5*7,因此
(4,420)(420,4)
(12,140)(140,12)12=4*3140=4*5*7
(20,84)(84,20)20=4*584=4*3*7
(28,60)(60,28)28=4*760=4*3*5
满足条件的(p、q)有8对。
tot←0;
{满足条件的(p、q)个数初始化}
ify0modx0=0{若y0不能整除x0,则不存在满足条件的(p,q)}
y←y0divx0;
{计算
=n=1*p1l1*p2l2*…pklk,确定满足条件的p和q有
}
fori←1totrunc(sqrt(y))do
if(ymodi=0)and(gcd(i,ydivi)=1)theninc(tot,2);
ify=1thendec(tot);
{若x0=y0,则(x0,y0)即为满足条件的(p,q)}
end;
输出满足条件的(p、q)个数tot;
【例题9.4】税收与补贴问题
每样商品的价格越低,其销量就会相应增大。
现已知某种商品的成本及其在若干价位上的销量(产品不会低于成本销售),并假设相邻价位销量的变化是线性的,且在价格高于给定的最高价后,销量以固定数值递减(假设价格和销量都是整数)。
对于某些特殊商品,不可能完全由市场去调节其价格。
这时候就需要政府以税收或补贴的方式来控制(所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币)。
你是某家咨询公司的项目经理,现在你已经知道政府对某种商品的预期价格,以及在各种价位上的销售情况。
要求你确定政府对此商品是应收税还是补贴的最小金额(也为整数),才能使商家在这样一种政府预期的价格上,获得相对其它价位上的最大利润。
总利润=单位利润*销量
单位商品利润=单位商品价格-单位商品成本(-税金OR+补贴)
输入
输入的第一行为政府对某种商品的预期价,第二行有两个整数,第一个整数为商品价格,第二个整数为以成本价销售时的销量,以下若干行每行都有两个整数,第一个为某价位时的单价,第二个为此时的销量,以一行-1、-1表示所有已知价及对应的销量输入完毕,输入的最后一行为一个单独的整数,表示在已知的最高价处每升高一元钱将减少的销量。
输出
输出有两种情况:
若在政府预期价上能得到最大利润,则输出一个单独的整数,数的大小表示补贴或收税的金额最小值。
若有多解,取绝对值最小的输出。
如在政府预期价上不能得到最大利润,则输出“NOSOLUTION”。
样例
31
28130
30120
31110
-1–1
15
许多选手对这道题一筹莫展。
除了对题型生疏的因素外,主要还是解题经验不足。
解题的前提和基础是正确审题。
对已知条件和解题目标的任何模糊认识,都会给解题过程带来困惑。
先不要苦思冥想于怎样解题,而是应该静下心来把题目多看几遍,真正弄明白试题要求我们做什么,为了达到这个目的,试题给出了或隐含了哪些关键条件。
然后籍助于我们的数学基础、解题经验包括灵感,寻求已知条件和解题目标之间的联系,即怎样解题的途径。
这道试题给出的已知条件,不仅包含了输入数据中政府预期价、各个价位的单价和销量等信息,更重要的是
⑴假设相邻价位销量的变化是线性的,且在价格高于给定的最高价后,销量以固定数值递减(假设价格和销量都是整数);
⑵给出了利润公式,所有价位都是依据这个公式计算利润的;
解题的目标是确定政府对此商品是应收税还是补贴的最小金额,使得商家在政府预期价格上的利润最大。
1.计算每个价位的总利润
设
t—价位数;
f—成本价的单价;
w—政府预期价;
d—最高单价处每升高一元将减少的销量;
l—前一次输入的商品单价;
a—价位销量表,其中a[i]为单价i时的销量;
试题明确“假设相邻价位销量的变化是线性的”。
当输入单价l和单价i的两个价位信息后(1≤l+1<
i),必须按照这一要求逐个计算单价l+1…单价i-1的销量,且每个价位k满足
a[k]=a[l]+
*(a[i]-a[l])(l+1≤k≤i-1)
同时,试题指出最高价处每升高一元钱将减少d个销量。
由此可见,价位表a共含t=最高价-f+1+
个连续价位。
a表的计算方法如下:
readln(w);
{读政府预期价}
l←0;
{前一次输入的商品单价初始化}
读第一个价位的单价i和销量j;
whilei≠-1do{若文件未输入完,则循环}
a[i]←j;
{定义单价为i时的销量}
ifl≠0{依次计算单价l+1..单价i-1的销量}
thenfork←l+1toi-1doa[k]←a[l]+(k-l)/(i-l)*(a[i]-a[l])
elsef←i;
{记下成本价}
l←i;
{记下刚输入的商品单价}
读下一个价位的单价i和销量j;
{while}
读最高价处升高一元将减少的销量d
i←l+1;
{计算最高价以上各价位的销量}
whilea[i-1]-d≥0do
begina[i]←a[i-1]-d;
i←i+1;
t←i-1;
{记下价位数}
2.计算政府控制量
按照利润公式,商家在政府预期价上的总利润为(w-f+x)*a[w]。
其中x为政府控制量:
x>
0时,x为政府补贴量;
x<
0时,
为商家交纳的税金;
这个总利润相对其它价位最大,即
1.f
x)*a[i]≤(w-f
x)*a[w](f≤i≤t,a[i]>
0,i≠w)
问题是,怎样计算政府控制量x。
由上述不等式可以得出
当政府控制量取+x时,
≤x;
当政府控制量取-x时,
≤x,即
≥
;
我们对a表中的除政府预期价外的每个单价i(f≤i≤t,a[i]>
0,i≠w)计算上述不等式:
当a[w]-a[i]>
0时,计算
的最大值min;
当a[w]-a[i]<
的最小值max;
由于x为整数,x>
0时min<
x、x<
0时max>
x,因此假设大于min的最小整数(上整
)可能为政府的最小补贴数;
小于max的最大整数(下整
)的绝对值可能为商家纳税的最小金额:
(注:
int为舍小数运算)
但
或
能否真正成为政府的控制量,还得具体分析:
⑴若
>
,则说明不等式矛盾,无解退出;
⑵若(
≤0)∧(
≥0),则说明即不收税也不补贴,输出0;
⑶若
0,则
为商家向政府交税的最小金额;
⑷若
≥0,则说明
为政府向商家补贴的最小值;
由此得出计算过程:
min←-maxint;
{补贴和收税金额的最小值初始化}
max←maxint;
fori←ftotdo{搜索政府预期价外每一个价位的销量}
if(i≠w)∧(a[i]>
thenbegin
b←a[w]-a[i];
c←a[i]*(i-f)-a[w]*(w-f);
ifb>
0{若政府预期价的销量大于单价i的销量,则计算补贴可能的最小值}
thenbeginifmin<
c/bthenmin←c/b;
end{then}
elseifmax>
c/bthenmax←c/b;
{若政府预期价的销量小于单价i的销量,则计算(-税金)可能的最大值}
min←
{补贴取上整}
max←
{税金取下整}
ifmin>
max{若不等式矛盾,则输出无解}
thenbegin
输出’NOSOLUTiON’;
halt;
if(min≤0)∧(max≥0){政府控制量为0}
输出0;
halt;
ifmax<
0then输出绝对值最小的收税额abs(max)
else输出补贴的最小值min;
9.2例题
2.一个矩阵的特征如下(n=5)
1341011
2591219
3.8131820
4.14172124
5.16222325
输入:
矩阵规模n(n≤50);
输出:
具有上述特征的矩。
6.找出n个正整数(≤2n=)用这些整数进行加法运算,使得包括原来的整数在内能组成尽可能多的不同整数。
n(n≤100);
所选的n个数;
能组成不同整数的个数。
7.有n个盒子(n≤1000),编号分别为1,2,…,n。
每个盒子可装入任何数量的球。
同时有k个小球(n≤k≤10000)。
小球装入盒子的规则:
⑴第1个盒子不空。
⑵装入必须按递增顺序进行。
例如当k=8、n=6时,装入方法有1、2、5或1、3、4
⑶在满足条件⑴⑵下,有球的盒子尽可能多。
⑷装完后,相邻盒子中球的全数差的绝对值之和最小(未装盒子不计)
例如上例中
装入法:
125134
差的绝对值之和:
2-1+5-2=43-1+4-3=3
n(盒子数)k(球数);
装入方法。
8.从边长为1的正方形出发可以用2个边长为1的正方形拼成面积为2的长方形;
用2个面积为2的长方形可拼出面积为4的长方形(包括正方形),这些面积为4的长方形如图9.2.1所示:
图9.2.1
用面积为4的长方形(包括正方形),可拼成两个面积为8的长方形。
这些面积为8的长方形如图9.2.2所示:
图9.2.2
可以按上述方法继续拼下去。
约定
1.边长对应相等的长方形被认为是相同的;
2.长度相等的边不能拼接,且两边必须重合;
n(1≤n≤109)
面积不超过n的所有可能拼法(ai,bi)(1≤i≤k),其中ai为第i种拼法的面积,bi为第i种拼法的种数。
9.AB两地的距离为S,甲、乙、丙三人从A到B共同完成任务。
从A地出发时,A地有X、Y两种出租车可供利用。
已知三人步行的速度都为a,出租车y的速度为b,仅能载一人;
出租车x的速度为c,能载二人(a<
b<
c)。
遗憾的是从A出发时x仅载一人,回头接人时才能载二人。
试问怎样安排行程才能使甲、乙、丙三人尽快同时到达B后共同完成任务。
10.现有一张由n个堡垒组成的交通图,任意两个堡垒之间只有一条通行路线。
为了确保路线畅通,必须在某些堡垒上建立火力中心,每个火力中心都能够对其相连的所有交通线进行全天候的监控,防止敌人侵略。
现在的问题是如何设置火力中心的布局,才能用最少的火力中心控制所有交通路线。
堡垒数n(1≤n≤10000);
以下每行为i,j,表示堡垒i与堡垒j连接。
以00标志结束;
火力中心数w;
以下有w行,每行为火力中心所在的堡垒号。
11.一群小朋友分两组,每组n个人围成一圈,编号为1‥n。
每人一个球,同组内的小球编号为1‥n。
所有小朋友闭上眼睛,一声哨响,每个小朋友用一只手把球传到右方,而用另一只手接左边的来球。
突然哨子停了,小朋友睁开眼睛,开始同组间传球,争取以最短时间将球传到位(即组内每一个小朋友手中小球的编号与自己的编号相同)。
如果哪一组出现球落地或一人手上拿多个球,则判该组输。
避免失误或犯规的方法是小球在两人之间对传。
注意对传可以同时进行。
比如小朋友1与小朋友2的对传和小朋友3与小朋友4的对传可以同时间进行,但被计作两次。
每一个时间单位内一个小朋友可以不做任何动作,亦可以与另外一个小朋友进行对传。
问题是怎么传,传给谁,才能使得组内所有小朋友的球最先传到位。
n(2≤n≤2000);
表示初始状态的n个数,其中第i个数为小朋友i手中球的编号;
a(至少需要a次对传才能将球传到位);
b(至少需要b时间才能将球传到位)。
12.敌人围攻W城,为了支援W城的保卫战,后方各基地纷纷通过直接运输或中途转运,将物质运往W城。
根据每条公路的长短和运输货物的多少,运输过程中会有不同程度的损耗。
假设每一条公路都有一个损耗系数,表示经过这条公路的物质总量与损耗量的比值。
另外为了保证物质运送安全,每个基地都会等所有要通过该基地转运的物质到齐后,连同本基地物质一起运往下一基地。
n(1‥n-1为基地编号,n为W城编号,2≤n≤100);
m(公路数);
n-1个整数,分别表示n-1个基地要运送的物质数量;
以下为m行,每行的格式为“ijk”,表示城市i与城市j之间有一条公路连接,该公路的损耗系数为k;
运到W城的最大物质数(保留两位小数);
n-1个数,其中第i个数为基地i将物质运往下一个基地或W城的编号。
13.某一地方的人说话半真半假。
某人询问了这个地方的n个居民,对于每个居民只问两个问题,每个居民只需对每个问题回答“是”或“否”,同一个问题可以反复问多个人。
根据居民的习俗,可以断定两个回答中有一个是正确的,而另一个是错误的。
某人需要对n个人的回答进行分析和整理,推断出所有问题的可能答案。
被询问的居民数n(1≤n≤10000)和问题数m(1≤m≤200)
以下为n行,其中第i行为“abcd”,表示第i个居民对问题a的回答是b,对问题c的回答是d(1≤a,c≤m;
0≤b,d≤1,0代表“否”,1代表“是”);
若不可能推出任何结果,则输出“noanswer”;
否则输出答案组的个数。
14.一个牧场为n*m的矩阵,每一个小方格可以安装电灯,电灯的照射范围为所在的小方格和周围8个小方格。
按照节约能源和所有小方格被照亮的要求,牧场应该安装多少灯,在那些位置上安装。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 开放性 试题
![提示](https://static.bingdoc.com/images/bang_tan.gif)