标题: 逻辑题：批处理求好学生的最大数量 [打印本页]
作者: 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个朋友时，只要比一人成绩好就是好学生了。
:- @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
作者: 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
原帖由 false:-) 于 2008-6-18 16:52 发表 
貌似朋友是互相的，这句话 只告诉我们 若a是b的朋友，那b也是a的朋友。。。我觉得仅有这一层含意而已~ 不包括“他若不是你朋友也就不是我朋友”
对啊，还是你说的有道理些。。。
作者: wankoilz 时间: 2008-6-18 20:09
发贴重复，已删除。
[ 本帖最后由 wankoilz 于 2008-6-18 20:17 编辑 ]
作者: wankoilz 时间: 2008-6-18 20:16
如果前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 编辑 ]
作者: xiaoxx 时间: 2008-6-21 19:19
一个班级中有30个学生，
(最多只能有30个好学生)
每个学生都有相同数量的朋友（自己不是自己的朋友，朋友是互相的），
(假如这帮学生都没有朋友=0)
如果某个学生比他这组朋友中的一半人学习好，
(0的一半还是0,所以满足比朋友组一半人学习好)
那么他就是一个好学生，
(他是好学生了)
求好学生的最大数量。。。
(30)
作者: 7babe 时间: 2008-6-23 17:35
原帖由 wankoilz 于 2008-6-18 20:16 发表 
如果前15名和后15名一一对应2人一组的话，也应该有15个优等生。
如果30个人组成一个30边形，每个点拥有的连线一样。如果是每个点都有29条连线，那仍然只有15个优等生...其他5或6人一组的情况也可以抽象成多边形的连 ...
我想，你的算法肯定不对，但我喜欢你的写法！
作者: Wiki 时间: 2018-9-24 10:14
有点晕了，但我喜欢
作者: hongrk 时间: 2019-4-6 15:55
本帖最后由 hongrk 于 2019-5-1 18:16 编辑
答案应该是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个
他们都是孤立的没有朋友聪明的人都很独立 因此没有朋友
| 欢迎光临 批处理之家 (http://bbs.bathome.net/) |
Powered by Discuz! 7.2 |