批处理之家's Archiver

pusofalse 发表于 2008-6-18 00:23

逻辑题:批处理求好学生的最大数量

题目是这样的:
一个班级中有30个学生,每个学生都有相同数量的朋友(自己不是自己的朋友,朋友是互相的),如果某个学生比他这组朋友中的一半人学习好,那么他就是一个好学生,求好学生的最大数量。。。

请用批处理求好学生的最大数量。。。
我初步计算的结果是14,想让达人们也做下这题,看答案是不是一样~谢谢。。。

随风 发表于 2008-6-18 00:40

具体还没想出来,但14应该不对,
假设每个学生都有4个朋友,那结果就应该是18了。

batman 发表于 2008-6-18 01:58

情况过于复杂,个人感觉用批处理来做很难!!!

随风 发表于 2008-6-18 02:39

先理解一下题意:
题:自己不是自己的朋友,朋友是互相的
理解:就是说你是我朋友,那么我就肯定是你朋友。他若不是你朋友也就不是我朋友。

题:如果某个学生比他“这组朋友中”的一半人学习好,那么他就是一个好学生
理解:那么也就是说当某人有2个朋友时,只要比一人成绩好就是好学生了。
:[code]@echo off&setlocal enabledelayedexpansion
for /l %%a in (1 1 29) do (
   set /a n=%%a+1,zu=30/n,k=n*zu
   if !k! equ 30 (
      set /a hao=^(%%a/2+1^)*zu
      if !hao! geq !num! set /a str=%%a,num=hao
      echo 每个同学 %%a 个朋友时共分 !zu! 组 每组 !n! 人 共 !hao! 个好学生
   ))
echo.
echo 每个同学 !str! 个朋友时好学生最多,共有 !num! 个好学生
pause>nul[/code]

pusofalse 发表于 2008-6-18 08:34

理解下题意。。。先假设这个班有4个学生。。。abcd,假设他们各自都有3个朋友,随机乱序给他们分配朋友
学生            朋友
a                              bcd
b                              acd
c                              abd
d                              abc

1.假设a比bc学习好,那么a为好学生,数量加1
2.因为第一步得出的结果,所以b不可能比a学习好。所以b只要比cd好,那么b为好学生,数量再加1
3.因为a>b>c,所以c只能比d学习好,那么c就不是好学生。。。
4.a>b>c>d 所以d不是好学生。。。。

这样一来,4个学生,每个学生三个朋友,那么好学生的数量就是2
请发现其中的规律。。。 这只是在假设朋友数量最大的情况下得出的结果。。。
我第一次得出的结果是错误的,忘记了是在求好学生的最大数量,应该把朋友的数量尽可能的减小。。。
是我把这题简单化了,实际情况过于复杂。正在思考版主的代码~

pusofalse 发表于 2008-6-18 10:59

不管怎么想,都是30组朋友才对 这个“组”是固定的~变化的是“组”里面的人数~

随风 发表于 2008-6-18 15:08

朋友是互相的
注意这句话的意思,
bcd 是一组的话 其他组就不可能还有 b或c或d 了的。

pusofalse 发表于 2008-6-18 16:52

貌似朋友是互相的,这句话 只告诉我们 若a是b的朋友,那b也是a的朋友。。。我觉得仅有这一层含意而已~ 不包括“他若不是你朋友也就不是我朋友”

我有点晕了。。。  这题有漏洞也说不定。。。

随风 发表于 2008-6-18 17:14

[quote]原帖由 [i]false:-)[/i] 于 2008-6-18 16:52 发表 [url=http://bathome.net/redirect.php?goto=findpost&pid=5335&ptid=1130][img]http://bathome.net/images/common/back.gif[/img][/url]
貌似朋友是互相的,这句话 只告诉我们 若a是b的朋友,那b也是a的朋友。。。我觉得仅有这一层含意而已~ 不包括“他若不是你朋友也就不是我朋友”

[/quote]

对啊,还是你说的有道理些。。。

wankoilz 发表于 2008-6-18 20:09

发贴重复,已删除。

[[i] 本帖最后由 wankoilz 于 2008-6-18 20:17 编辑 [/i]]

wankoilz 发表于 2008-6-18 20:16

如果前15名和后15名一一对应2人一组的话,也应该有15个优等生。
如果30个人组成一个30边形,每个点拥有的连线一样。如果是每个点都有29条连线,那仍然只有15个优等生...其他5或6人一组的情况也可以抽象成多边形的连线。
若总人数n,貌似最多的优等生数量为 n/2 或 (n-1)/2

写了个,不知道对不对:
[code]@echo off
set/p num=请输入班上的人数:
cls&echo 总人数%num%,每个人有相同的朋友数,优等生情况如下:&echo.
for /l %%i in (2,1,%num%) do (
call :out %%i
)
pause>nul
:out
set/a t=1/(num%%%1) 2>nul && goto :eof || set/a m=%1,n=num/m,q=%1-1
set/a t=1/(m%%2) 2>nul && set/a o=(m-1)/2 || set/a o=m/2
set/a p=o*n
echo 如果每个人有%q%个朋友,那么有%p%个优等生。[/code]

[[i] 本帖最后由 wankoilz 于 2008-6-19 20:56 编辑 [/i]]

xiaoxx 发表于 2008-6-21 19:19

一个班级中有30个学生,
(最多只能有30个好学生)
每个学生都有相同数量的朋友(自己不是自己的朋友,朋友是互相的),
(假如这帮学生都没有朋友=0)
如果某个学生比他这组朋友中的一半人学习好,
(0的一半还是0,所以满足比朋友组一半人学习好)
那么他就是一个好学生,
(他是好学生了)
求好学生的最大数量。。。
(30)

7babe 发表于 2008-6-23 17:35

[quote]原帖由 [i]wankoilz[/i] 于 2008-6-18 20:16 发表 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=5342&ptid=1130][img]http://bbs.bathome.net/images/common/back.gif[/img][/url]
如果前15名和后15名一一对应2人一组的话,也应该有15个优等生。
如果30个人组成一个30边形,每个点拥有的连线一样。如果是每个点都有29条连线,那仍然只有15个优等生...其他5或6人一组的情况也可以抽象成多边形的连 ... [/quote]

我想,你的算法肯定不对,但我喜欢你的写法!

Wiki 发表于 2018-9-24 10:14

有点晕了,但我喜欢

hongrk 发表于 2019-4-6 15:55

[i=s] 本帖最后由 hongrk 于 2019-5-1 18:16 编辑 [/i]

答案应该是29(没有朋友是30,当然是最多,但这样似乎不太符合题目的意思……)。
不过我只是从逻辑上推出来的,还没有写出批处理。这道题我对直接写批没有什么想法,是打算推导出公式后直接让批处理算公式……

解:
这里把学生按顺序排为1 2 3 4……28 29 30,不妨设后者比前者学习更好。
则每个学生都各有2个朋友时,令每个学生的朋友为其前一位与后一位(如2则对于1、3,1则对于30、2)
如是,则根据题目要求,好学生有29个。只有学习最差的1不是好学生。

又因为30个学生不可能全为好学生(否则用来对比的那个学生是谁),所以29就是最大值。

对于普遍些的情况,设y为好学生总数,x为学生总数,n为一个学生有多少朋友。则好学生需要至少比m=floor[(n+1)/2]个朋友学习好。
n为偶数时,有y=x-m。如x=5,n=2时,可列出以下数列:123,234,345,451,512. 把每一项的中心当成一个学生,则其前后则为Ta的朋友。这样可以保证除了比其他人学习都好的那个人之外,其他好学生都恰恰比m个朋友学习好,实现最大化利用。此时显然只有成绩最差的m个学生不是好学生(此例中为1),故y=x-m=x-n/2
由此也可以直接推出1楼问题的结果,n=0时y最大,为30……

n为奇数就比较麻烦。

若x同时为奇数,则根本无法进行分组。即不能够实现题目要求的“每个学生都有相同数量的朋友”。
若x为偶数,则我还无从下手。使用@wankoilz的多边形法,能确定x≦6时都能分组,且最大结果都符合y=x-m。(除n=1外,则y=x/2)
但,x=8, n=3时,基本确定这个极限值是无法达到的;即只能做到y=x-m-1。我没有再向下。

在此抛砖引玉。

smss 发表于 2019-4-6 16:15

条件1和2没有直接关系  这求最大值时就应该这好学生有30个

他们都是孤立的没有朋友聪明的人都很独立 因此没有朋友{:2_30:}

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.