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

pusofalse

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

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

smss

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

他们都是孤立的没有朋友聪明的人都很独立 因此没有朋友

hongrk

答案应该是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。我没有再向下。

在此抛砖引玉。

Wiki

有点晕了，但我喜欢

7babe

原帖由 wankoilz 于 2008-6-18 20:16 发表
如果前15名和后15名一一对应2人一组的话，也应该有15个优等生。
如果30个人组成一个30边形，每个点拥有的连线一样。如果是每个点都有29条连线，那仍然只有15个优等生...其他5或6人一组的情况也可以抽象成多边形的连 ...

我想，你的算法肯定不对，但我喜欢你的写法！

xiaoxx

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

wankoilz

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

写了个，不知道对不对:

@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%个优等生。
复制代码

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

wankoilz

发贴重复，已删除。

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

随风

原帖由 false:-) 于 2008-6-18 16:52 发表
貌似朋友是互相的，这句话 只告诉我们 若a是b的朋友，那b也是a的朋友。。。我觉得仅有这一层含意而已~ 不包括“他若不是你朋友也就不是我朋友”

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

pusofalse

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

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

随风

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

pusofalse

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

pusofalse

理解下题意。。。先假设这个班有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
请发现其中的规律。。。 这只是在假设朋友数量最大的情况下得出的结果。。。
我第一次得出的结果是错误的，忘记了是在求好学生的最大数量，应该把朋友的数量尽可能的减小。。。
是我把这题简单化了，实际情况过于复杂。正在思考版主的代码~

随风

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

题：如果某个学生比他“这组朋友中”的一半人学习好，那么他就是一个好学生
理解：那么也就是说当某人有2个朋友时，只要比一人成绩好就是好学生了。
:

@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
复制代码

batman

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