----在写一道程序的时候，遇到一个很扭的算法，当中涉及到离散数学的知识。糟糕的是：上《离散数学》课时经常逃课，现在想来真后悔...现在我想都想出来:(
女生的推理思维真的那么差劲吗？:( 泄气都没用了，现在我只能求助于各位大虾了，如果谁能在下个星期三之前提出一些有用的意见，这里的35分(怎么才能吧给分加到100分？）就贡送出去！
请看下面：
已知一个二分图G=(A,B,E)，满足|B|<|A|<2|B|
对于每个节点Xi属于A,都有d(Xi)=3,即存在Yj,Yk,Yp属于B,
使得(Xi,Yi),(Xi,Yk),(Xi,Yk)属于E,
那么，能否得到这么一个二分图G'=(A,B,E')
对于每个节点Xi属于A,都有1<=d(Xi)<=2;
至少存在Yi属于B,使得(Xi,Yi)属于E',
并且对于每个Yi属于B,满足d(Yi)<=Pi(Pi为一个常数).
26 个解决方案
#1
啥是离散数学 哈哈哈哈哈
#2
,.
#3
我《离散数学》课逃得比你还多，看来帮不上忙了
#4
不好意思我是大一的，在上高等数学。
#5
我是不是帖错地方了？这里是C++论坛吧？怎么没有人回答我的问题呢？
#6
呵呵，你好像是帖错地方了，放到数据算法论坛去吧，这儿还记得离散数学的人不多：）
#7
@_@
#8
不明白这和女生不灵有什么关系？你是女生？
#9
这种东西男生也没几个懂的。
不过题目的表达有点不清楚，是照抄源题吗？而且至少存在Yi属于B,使得(Xi,Yi)属于E'不是由对于每个节点Xi属于A,都有1<=d(Xi)<=2已经可以得出了吗？还有是否要求E'是E的子集？还有是不是要求Pi对所有的这样的图G都成立？如果那样就不一定了。
另外建议转到数据算法版，稍微合理一点。
不过题目的表达有点不清楚，是照抄源题吗？而且至少存在Yi属于B,使得(Xi,Yi)属于E'不是由对于每个节点Xi属于A,都有1<=d(Xi)<=2已经可以得出了吗？还有是否要求E'是E的子集？还有是不是要求Pi对所有的这样的图G都成立？如果那样就不一定了。
另外建议转到数据算法版，稍微合理一点。
#10
整体来说，男生的数学强于女生，女生的英语强于男生，这是事实，正如中国的古迹文物比美国要多历史要深厚，美国佬的*工作做得到位些腐败少些，这也是事实，没必要因为我是尊重女性就否认前者，也不会因为我们是“公仆们”所说的“当了家作了主的主人”就否认后者。
理性思考才会有*和法治。
理性思考才会有*和法治。
#11
F.H!
#12
那也就是说，你们在写程序的时候很少甬到《离散数学》、《高数》呢？
我现在还在大学里，二年级的，还没有写过一道真真的有使用价值的程序，所以我还不知道要成为一名程序员应该具备什么知识，数学会不会很重要呢？要是那样的话就糟了，我的数学学的不好，大一时没把高数学好。。。
:(
这一道题是我想的，我们老师写了一道程序，是用来选修的，也就是说有n个学生要学修，然后名额有限，有的保证每个学生都能选到一课，然后每个科目的名额都是有限的，要怎么才能实现呢（最好就是让我们系的同学都能选上两门了:)..)?有的保证执行速度快，所以我就想到了用离散来做，结果我太笨了，现在还是找不到解决办法，
那位大虾能帮一帮呢？
to feta(飞天一剑), 你的话我不太明白，就是小鸟不想飞了，我还是想飞，这叫着--被鸟先飞！我想我是笨了一些，可是既然我选择了这一专业，我就会喜欢他，就像你们喜欢你们的情人一样，我来这儿就是想在这里淘金吧！
其实我挺喜欢这儿的，只是这里的水太多了，
我现在还在大学里，二年级的，还没有写过一道真真的有使用价值的程序，所以我还不知道要成为一名程序员应该具备什么知识，数学会不会很重要呢？要是那样的话就糟了，我的数学学的不好，大一时没把高数学好。。。
:(
这一道题是我想的，我们老师写了一道程序，是用来选修的，也就是说有n个学生要学修，然后名额有限，有的保证每个学生都能选到一课，然后每个科目的名额都是有限的，要怎么才能实现呢（最好就是让我们系的同学都能选上两门了:)..)?有的保证执行速度快，所以我就想到了用离散来做，结果我太笨了，现在还是找不到解决办法，
那位大虾能帮一帮呢？
to feta(飞天一剑), 你的话我不太明白，就是小鸟不想飞了，我还是想飞，这叫着--被鸟先飞！我想我是笨了一些，可是既然我选择了这一专业，我就会喜欢他，就像你们喜欢你们的情人一样，我来这儿就是想在这里淘金吧！
其实我挺喜欢这儿的，只是这里的水太多了，
#13
哈哈，不在乎多我再添点水吧....
#14
女孩子是感性思维见长嘛，写程序，算法需要理性思维更多一点。
#15
To:thcay(不想说) :
不好意思 ：）请问理性思维是什么意思？
看来我是要放弃这个程序呢？有点伤心:(
不好意思 ：）请问理性思维是什么意思？
看来我是要放弃这个程序呢？有点伤心:(
#16
程序是艺术品，编程是艺术创作。
艺术是什么思维？
艺术是什么思维？
#17
我有一个朋友学计算机的，可被抓的课都是计算机专业课程，好像离散也是其中一门。呵呵呵
#18
离散数学是专业课,那一个学期我就去听了一节,结果......可想而知...自然是......
书到用时方恨少........
现在看到这个我都一个脑袋两个大......
书到用时方恨少........
现在看到这个我都一个脑袋两个大......
#19
这东西，几天不用就忘了！
想当年我的离散学的挺好的，可现在连题都看不懂了，呜^^^^^^^^^^^^^^^^^^^
想当年我的离散学的挺好的，可现在连题都看不懂了，呜^^^^^^^^^^^^^^^^^^^
#20
OVER?
#21
哇，ＭＭ ：)
爱莫能助 ：(
爱莫能助 ：(
#22
玩完……
不懂………
不懂………
#23
谁认识"何奉道"的? 老子的离散数学在他手里栽过!!!
#24
你的模型很对,但是不保证有解,比如所有学生都选同样的3门课, 这样就很可能对于给订的每门课的学生名额Pi,不能得到你要的图.
而且我认为Pi可能应该是个B -> int的函数, 难道每门课都是一样的学生名额?
我展示没什么好算法, 你可以时时:
大致是定义一个叔祖
d(Yi) where Yi is in B
由小到大排序
然后按照这个顺序排列Yi,
令开始R=A
procedure F(Yi):
1. 在R里与Yi相连的d(Yi)条边里找出PI(Yi)条边,不够没关系,这是在枚举每一种组合,
2. 对于当前挑出的一种组合:{(Xk,Yi)|0 < k <= PI(Yi), Xk is in R}, 将与Yi相连的属于A的节点集合{Xk}从R中减去,同时纪录它们的课程为Yi
3. 如果R为空, 则所有学生都有课上了, 退出程序. 否则调用F(Y_i+1_)来对下面1门课进行分配.
4. 如果返回这里表明分配不成功, 则如果可以挑出下一个边组合, 就返回2继续试, 没有组合了就返回上层调用者.
如果第一层调用者也找不到而返回, 那么就无解了.
注意d(Yi)是变化的,因为R是变化的.
如果有解的话,我想程序应该很快就找出来,但要便利所有组合才能知道无解.
建议的不好,仅供参考.
而且我认为Pi可能应该是个B -> int的函数, 难道每门课都是一样的学生名额?
我展示没什么好算法, 你可以时时:
大致是定义一个叔祖
d(Yi) where Yi is in B
由小到大排序
然后按照这个顺序排列Yi,
令开始R=A
procedure F(Yi):
1. 在R里与Yi相连的d(Yi)条边里找出PI(Yi)条边,不够没关系,这是在枚举每一种组合,
2. 对于当前挑出的一种组合:{(Xk,Yi)|0 < k <= PI(Yi), Xk is in R}, 将与Yi相连的属于A的节点集合{Xk}从R中减去,同时纪录它们的课程为Yi
3. 如果R为空, 则所有学生都有课上了, 退出程序. 否则调用F(Y_i+1_)来对下面1门课进行分配.
4. 如果返回这里表明分配不成功, 则如果可以挑出下一个边组合, 就返回2继续试, 没有组合了就返回上层调用者.
如果第一层调用者也找不到而返回, 那么就无解了.
注意d(Yi)是变化的,因为R是变化的.
如果有解的话,我想程序应该很快就找出来,但要便利所有组合才能知道无解.
建议的不好,仅供参考.
#25
还有如果事先将选课情况一样的学生归堆,枚举组合的时候作为无差别元素,可以大大减少可能的组合数
#26
谢谢各位，我现在给分了
#1
啥是离散数学 哈哈哈哈哈
#2
,.
#3
我《离散数学》课逃得比你还多，看来帮不上忙了
#4
不好意思我是大一的，在上高等数学。
#5
我是不是帖错地方了？这里是C++论坛吧？怎么没有人回答我的问题呢？
#6
呵呵，你好像是帖错地方了，放到数据算法论坛去吧，这儿还记得离散数学的人不多：）
#7
@_@
#8
不明白这和女生不灵有什么关系？你是女生？
#9
这种东西男生也没几个懂的。
不过题目的表达有点不清楚，是照抄源题吗？而且至少存在Yi属于B,使得(Xi,Yi)属于E'不是由对于每个节点Xi属于A,都有1<=d(Xi)<=2已经可以得出了吗？还有是否要求E'是E的子集？还有是不是要求Pi对所有的这样的图G都成立？如果那样就不一定了。
另外建议转到数据算法版，稍微合理一点。
不过题目的表达有点不清楚，是照抄源题吗？而且至少存在Yi属于B,使得(Xi,Yi)属于E'不是由对于每个节点Xi属于A,都有1<=d(Xi)<=2已经可以得出了吗？还有是否要求E'是E的子集？还有是不是要求Pi对所有的这样的图G都成立？如果那样就不一定了。
另外建议转到数据算法版，稍微合理一点。
#10
整体来说，男生的数学强于女生，女生的英语强于男生，这是事实，正如中国的古迹文物比美国要多历史要深厚，美国佬的*工作做得到位些腐败少些，这也是事实，没必要因为我是尊重女性就否认前者，也不会因为我们是“公仆们”所说的“当了家作了主的主人”就否认后者。
理性思考才会有*和法治。
理性思考才会有*和法治。
#11
F.H!
#12
那也就是说，你们在写程序的时候很少甬到《离散数学》、《高数》呢？
我现在还在大学里，二年级的，还没有写过一道真真的有使用价值的程序，所以我还不知道要成为一名程序员应该具备什么知识，数学会不会很重要呢？要是那样的话就糟了，我的数学学的不好，大一时没把高数学好。。。
:(
这一道题是我想的，我们老师写了一道程序，是用来选修的，也就是说有n个学生要学修，然后名额有限，有的保证每个学生都能选到一课，然后每个科目的名额都是有限的，要怎么才能实现呢（最好就是让我们系的同学都能选上两门了:)..)?有的保证执行速度快，所以我就想到了用离散来做，结果我太笨了，现在还是找不到解决办法，
那位大虾能帮一帮呢？
to feta(飞天一剑), 你的话我不太明白，就是小鸟不想飞了，我还是想飞，这叫着--被鸟先飞！我想我是笨了一些，可是既然我选择了这一专业，我就会喜欢他，就像你们喜欢你们的情人一样，我来这儿就是想在这里淘金吧！
其实我挺喜欢这儿的，只是这里的水太多了，
我现在还在大学里，二年级的，还没有写过一道真真的有使用价值的程序，所以我还不知道要成为一名程序员应该具备什么知识，数学会不会很重要呢？要是那样的话就糟了，我的数学学的不好，大一时没把高数学好。。。
:(
这一道题是我想的，我们老师写了一道程序，是用来选修的，也就是说有n个学生要学修，然后名额有限，有的保证每个学生都能选到一课，然后每个科目的名额都是有限的，要怎么才能实现呢（最好就是让我们系的同学都能选上两门了:)..)?有的保证执行速度快，所以我就想到了用离散来做，结果我太笨了，现在还是找不到解决办法，
那位大虾能帮一帮呢？
to feta(飞天一剑), 你的话我不太明白，就是小鸟不想飞了，我还是想飞，这叫着--被鸟先飞！我想我是笨了一些，可是既然我选择了这一专业，我就会喜欢他，就像你们喜欢你们的情人一样，我来这儿就是想在这里淘金吧！
其实我挺喜欢这儿的，只是这里的水太多了，
#13
哈哈，不在乎多我再添点水吧....
#14
女孩子是感性思维见长嘛，写程序，算法需要理性思维更多一点。
#15
To:thcay(不想说) :
不好意思 ：）请问理性思维是什么意思？
看来我是要放弃这个程序呢？有点伤心:(
不好意思 ：）请问理性思维是什么意思？
看来我是要放弃这个程序呢？有点伤心:(
#16
程序是艺术品，编程是艺术创作。
艺术是什么思维？
艺术是什么思维？
#17
我有一个朋友学计算机的，可被抓的课都是计算机专业课程，好像离散也是其中一门。呵呵呵
#18
离散数学是专业课,那一个学期我就去听了一节,结果......可想而知...自然是......
书到用时方恨少........
现在看到这个我都一个脑袋两个大......
书到用时方恨少........
现在看到这个我都一个脑袋两个大......
#19
这东西，几天不用就忘了！
想当年我的离散学的挺好的，可现在连题都看不懂了，呜^^^^^^^^^^^^^^^^^^^
想当年我的离散学的挺好的，可现在连题都看不懂了，呜^^^^^^^^^^^^^^^^^^^
#20
OVER?
#21
哇，ＭＭ ：)
爱莫能助 ：(
爱莫能助 ：(
#22
玩完……
不懂………
不懂………
#23
谁认识"何奉道"的? 老子的离散数学在他手里栽过!!!
#24
你的模型很对,但是不保证有解,比如所有学生都选同样的3门课, 这样就很可能对于给订的每门课的学生名额Pi,不能得到你要的图.
而且我认为Pi可能应该是个B -> int的函数, 难道每门课都是一样的学生名额?
我展示没什么好算法, 你可以时时:
大致是定义一个叔祖
d(Yi) where Yi is in B
由小到大排序
然后按照这个顺序排列Yi,
令开始R=A
procedure F(Yi):
1. 在R里与Yi相连的d(Yi)条边里找出PI(Yi)条边,不够没关系,这是在枚举每一种组合,
2. 对于当前挑出的一种组合:{(Xk,Yi)|0 < k <= PI(Yi), Xk is in R}, 将与Yi相连的属于A的节点集合{Xk}从R中减去,同时纪录它们的课程为Yi
3. 如果R为空, 则所有学生都有课上了, 退出程序. 否则调用F(Y_i+1_)来对下面1门课进行分配.
4. 如果返回这里表明分配不成功, 则如果可以挑出下一个边组合, 就返回2继续试, 没有组合了就返回上层调用者.
如果第一层调用者也找不到而返回, 那么就无解了.
注意d(Yi)是变化的,因为R是变化的.
如果有解的话,我想程序应该很快就找出来,但要便利所有组合才能知道无解.
建议的不好,仅供参考.
而且我认为Pi可能应该是个B -> int的函数, 难道每门课都是一样的学生名额?
我展示没什么好算法, 你可以时时:
大致是定义一个叔祖
d(Yi) where Yi is in B
由小到大排序
然后按照这个顺序排列Yi,
令开始R=A
procedure F(Yi):
1. 在R里与Yi相连的d(Yi)条边里找出PI(Yi)条边,不够没关系,这是在枚举每一种组合,
2. 对于当前挑出的一种组合:{(Xk,Yi)|0 < k <= PI(Yi), Xk is in R}, 将与Yi相连的属于A的节点集合{Xk}从R中减去,同时纪录它们的课程为Yi
3. 如果R为空, 则所有学生都有课上了, 退出程序. 否则调用F(Y_i+1_)来对下面1门课进行分配.
4. 如果返回这里表明分配不成功, 则如果可以挑出下一个边组合, 就返回2继续试, 没有组合了就返回上层调用者.
如果第一层调用者也找不到而返回, 那么就无解了.
注意d(Yi)是变化的,因为R是变化的.
如果有解的话,我想程序应该很快就找出来,但要便利所有组合才能知道无解.
建议的不好,仅供参考.
#25
还有如果事先将选课情况一样的学生归堆,枚举组合的时候作为无差别元素,可以大大减少可能的组合数
#26
谢谢各位，我现在给分了