徽章问题--数学建模.doc

第八届本科生学科大赛2014数学建模竞赛承 诺 书我们仔细阅读了河西学院大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性.如有违反竞赛规则的行为，我们将受到严肃处理.我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 参赛队员 (打印并签名) ：序号姓 名(打印)所在学院签 名123指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日评阅编号（由竞赛组委会评阅前进行编号）：第八届大学生学科大赛2014年数学建模竞赛评 阅 专 用 页评阅编号（由竞赛组委会评阅前进行编号）：评阅记录（供竞赛组委会评阅时使用）：评阅人评分备注评阅结果：获奖等级：徽章问题摘要: 在此次会议中，代表们收到不同标记的徽章，与他们的名字有关，所以按照一定的原理，我们建立模型，首先，我们将286名代表按照所收到的徽章标记“+”和“-”进行分类，把收到“+”标记徽章的代表们的名字记作向量,把收到“-”标记徽章的代表们的名字记作向量，其中.再利用编程VC+程序，对对向量和向量中的第个分量分别进行观察、对比，得出向量和向量中的第个分量都分别有交叉项，则排除以这些分量的特性为分类依据的方法，但是和向量中第2个分量没有交叉量，且第二个分量都属于即.因此，对于猜想徽章标记于第二个分量有关，进而得出了对徽章的分类给出了方法，即代表们的名字的第二个字母在内是，徽章标记为“+”，反之，徽章标记为“-”.对于第二题，我们根据问题一的解答，如果名字的第二个字母为大写时，直接给与”-”标记，则准确率为100%，则错误率为0;如如果名字的第二个字母为大写时，仍然按照问题一的分类方法，则正确率为99.49%，则错误率为0.51%. 对于问题三，我们按照以上得出的分类方法，通过编写程序利用VC+程序，对未参加会议的14名代表进行了分类，最后只有Attilio Giordana的徽章为“-”，其它代表的徽章都为“+”.最后，我们对这个模型评价，本题的优点是数据量有限，有利于建模的假设与解答;不足之处是，这个模型虽然检验结果与实际的相当吻合，但该模型存在着随机性，如果参加会议的代表人数曾多，这个模型还会继续有效吗？因此，我们提出改进，加强分类的指标和条件，例如以前2个字母，前3个字母等其他方法进行分析、讨论，尝试分类，使得分得的两组的人数在理论上相等.关键字：字母；分量；排序;分类一 问题重述在1994年的“机器学习与计算学习理论”的国际会议上，参加会议的280名代表都收到会议组织者发给的一枚徽章，徽章的标记为“”或“”（参加会议的名单及得到的徽章见附表）.会议组织者声明：每位代表得到徽章“”或“”的标记只与他们的姓名有关，并希望代表们能够找出徽章“”与“”的分类方法.问题如下：1如何对参加会议的代表所得的的徽章找出合理的规律进行分类.2对自己的分类方法进行分析，如分类的理由、分类的规律、分类的正确率与错误率等.3、由于客观原因，有14名代表（见附表）没能参加此次会议.按照以上找出的方法，如果他们参加会议，他们将得到什么类型的徽章？ 二 模型假设首先，我们将286名代表按照所收到的徽章标记“+”和“-”进行分类，假设得到徽章只与代表的名字有关系.把收到“+”标记徽章的代表们的名字记作向量，其中，把收到“-”标记徽章的代表们的名字记作向量，其中，把代表们名字中的字母按在名字中的排序分别作为这个向量的第一个分量，第二个分量，第七个分量（因为代表们名字中最短的名字只要七个字母，Ken Lang）,同时在把代表们的名字记为向量时，给26个字母（按字母表的顺序）分别赋值为01,02，26.例如第一个收到“+”的代表Naoki Abe的名字用向量表示为，第一个收到“-”的代表Myrian Abramson的名字用向量表示为.然后利用VC+编程，对向量和向量中的第个分量分别进行观察、对比.(1)题中所给的人名是英文名字，由英语知识可知，外国人的姓名顺序与中国人相反，即名在前，姓在后.因此我们猜想，徽章的标记跟向量和向量中的第个分量有关的概率相对较大.(2)一旦得出的徽章分类方法的正确率较高时（不妨为90%以上），那就采取这种分类方法.三 模型建立模型1 利用VC+编程，对向量和向量中的第 个分量分别进行观察、对比，（程序见附件1）结果如下： 由以上结果得到：向量和向量中的第个分量都分别有交叉项，则排除以这些分量的特性为分类依据的方法，但是向量和向量中第2个分量没有交叉量，且向量的第二个分量都属于即第二个字母属于.因此，我们猜想徽章标记与第二个分量有关.模型2 我们在先向量后向量排序基础上再按向量和向量中的第二个分量的顺序进行排序,如下：徽章符号向量中的第二个分量名字中的第二个字母代表们的名字代表们的姓氏+01aJavedAslam+01aDavidW. Aha+01a+05ePeterBartlett+05eGeorgeBerg+05e+09iTimothyP. Barber+09iMichaelW. Barley+09i+15oTomBylander+15oJohnCase+15o+21uSusanL. Epstein+21uJudyA. Franklin+21u-02bR. BharatRao-03cScottE. Decatur-04dOdedMaron-01至26中除去01,05,09,15,21除a、e、i、o、u字母外 表（1）由上述表格可以看出：（1） 当代表们名字的第二个字母为元音（a、e、i、o、u）并且为小写字母时，他们得到的徽章标记均为“+”号，否则为“-”号.（2）当名字的第二个字母为大写时，则他们得到的徽章均为“-”号，例如：R. Andrew McCallum L. Thorne McCarty 等等.四 模型求解（1）徽章的分类方法：参加会议的代表们的名字中的第二个字母为元音字母并且为小写时，他们均得到带“+”号标记的徽章；否则均得到带“-”号标记的徽章.（2）分类的理由：由于代表们所收到的徽章的标记只与他们的名字有关，所以先以徽章标记“+”和“-”分析，得出猜想，再以名字中的第二个字母进行排序、比较、分析，最后得出分类方法，见模型2.分类的正确与错误率：参加会议的代表们的总人数为286，我们根据(1)题的分类方法，如果名字的第二个字母为大写时，直接给”-”标记，则准确率为100%，见表(1),从而错误率为0;如果名字的第二个字母为大写时，仍然按照(1)题的分类方法，则正确率为99.49%，则错误率为0.51%.（3）根据我们的假设(若正确率达到90%，则此方法可行)及题(1)得出的分类方法，于是通过编写程序利用VC+软件，对未参加会议的14名代表进行了分类，程序见（附件2），结果如下：由上边结果知：只有Attilio Giordana的徽章为“-”，其它代表的徽章都为“+”.五 模型评价及改进本题的优点是数据量有限，有利于建模的假设与解答;不足之处是，这个模型虽然检验结果与本次会议中给出的数据实际的相当吻合，但该模型存在着随机性，如果参加会议的代表人数曾多，这个模型还会继续有效吗？并且在这些代表中收到”+”号标记的人数为196人，收到”-”号标记的人数为90人，这种分类方法是不好的，因为在做决策，裁定时，这种分类方法使解决问题变的不公平、不平等.因此，我们提出改进，加强分类的指标和条件，例如以前2个字母，前3个字母等其他方法进行分析、讨论，尝试分类，使得分得的两组的人数在理论上相等.参考文献1 姜启源,叶俊等.数学模型第三版.高等教育出版社，北京，20042 康博创作室.VC+6.0高级编程.清华大学出版社，北京，19993 谭浩强著.C程序设计(第四版).北京：清华大学出版社，2010.64 袁震东，洪渊，林武忠，蒋鲁敏编著.数学建模.华东师范大学出版社，1995.55 高隆昌，杨元著.数学建模基础理论.北京：科学出版社，2007附件1#includeusing namespace std;int main()char letter30= ;int count=0,flag=0;char name28030=+Naoki Abe, -Myriam Abramson,+David W. Aha,+Kamal M. Ali ,-Eric Allender , +Dana Angluin,-Chidanand Apte,+Minoru Asad,+Lars Asker,+Javed Aslam,+Haralabos Athanassiou,+Jose L. Balcazar,+Timothy P. Barber,+Michael W. Barley, -Cristina Baroglio,+Peter Bartlett,-Eric Baum,+Welton Becket,-Shai Ben-David, +George Berg,+Neil Berkman,+Malini Bhandaru,+Bir Bhanu,+Reinhard Blasig,-Avrim Blum,-Anselm Blumer ,+Justin Boyan,+Carla E. Brodley,+Nader Bshouty,-Wray Buntine,-Andrey Burago,+Tom Bylander,+Bill Byrne,-Claire Cardie, +Richard A. Caruana,+John Case,+Jason Catlett,+Nicolo Cesa-Bianchi,-Philip Chan,+Mark Changizi ,+Pang-Chieh Chen ,-Zhixiang Chen,+Wan P. Chiang, -Steve A. Chien,+Jeffery Clouse,+William Cohen,+David Cohn ,-Clare Bates Congdon,-Antoine Cornuejols,+Mark W. Craven,+Robert P. Daley,+Lindley Darden, -Chris Darken,-Bhaskar Dasgupta,-Brian D. Davidson,+Michael de la Maza,-Olivier De Vel,-Scott E. Decatur,+Gerald F. DeJong,+Kan Deng,-Thomas G. Dietterich,+Michael J. Donahue,+George A. Drastal,+Harris Drucker,-Chris Drummond,+Hal Duncan,-Thomas Ellman, +Tapio Elomaa,+Susan L. Epstein,+Bob Evans ,-Claudio Facchinetti,+Tom Fawcett,-Usama Fayyad,+Aaron Feigelson,+Nicolas Fiechter,+David Finton ,+John Fischer,+Paul Fischer,+Seth Flanders,+Lance Fortnow,-Ameur Foued,+Judy A. Franklin,+Yoav Freund,+Johannes Furnkranz,+Leslie Grate,+William A. Greene,+Russell Greiner,+Marko Grobelnik,+Tal Grossman , +Margo Guertin,+Tom Hancock,+Earl S. Harris Jr.,+David Haussler,+Matthias Heger, +Lisa Hellerstein,+David Helmbold,+Daniel Hennessy,+Haym Hirsh,+Jonathan Hodgson,+Robert C. Holte,+Jiarong Hong,-Chun-Nan Hsu,+Kazushi Ikeda,+Masayuki Inaba,-Drago Indjic,+Nitin Indurkhya,+Jeff Jackson,+Sanjay Jain,+Wolfgang Janko,-Klaus P. Jantke,+Nathalie Japkowicz,+George H. John,+Randolph Jones,+Michael I. Jordan,+Leslie Pack Kaelbling,+Bala Kalyanasundaram,-Thomas E. Kammeyer,-Grigoris Karakoulas,+Michael Kearns,+Neela Khan,+Roni Khardon,+Dennis F. Kibler ,+Jorg-Uwe Kietz,-Efim Kinber,-Jyrki Kivinen,-Emanuel Knill,-Craig Knoblock,+Ron Kohavi,+Pascal Koiran,+Moshe Koppel,+Daniel Kortenkamp,+Matevz Kovacic,-Stefan Kramer,+Martinch Krikis,+Martin Kummer,-Eyal Kushilevitz,-Stephen Kwek ,+Wai Lam,+Ken Lang,-Steffen Lange, +Pat Langley,+Mary Soon Lee,+Wee Sun Lee,+Moshe Leshno,+Long-Ji Lin, -Charles X. Ling, +Michael Littman,+David Loewenstern,-Phil Long, +Wolfgang Maass,-Bruce A. MacDonald,+Rich Maclin,-Sridhar Mahadevan,-J.Jeffrey Mahoney,+Yishay Mansour,+Mario Marchand,-Shaul Markovitch,-Oded Maron, +Maja Mataric,+David Mathias,+Toshiyasu Matsushima,-Stan Matwin,-Eddy Mayoraz ,-R. Andrew McCallum,-L.Thorne McCarty,-Alexander M. Meystel,+Michael A. Meystel ,-Steven Minton,+Nina Mishra,+Tom M. Mitchell,+Dunja Mladenic,+David Montgomery,-Andrew W. Moore,+Johanne Morin,+Hiroshi Motoda,-Stephen Muggleton ,+Patrick M. Murphy,-Sreerama K. Murthy,+Filippo Neri,-Craig Nevill-Manning,-Andrew Y. Ng,+Nikolay Nikolaev,-Steven W. Norton,+Joseph OSullivan,+Dan Oblinger,+Jong-Hoon Oh,-Arlindo Oliveira,+David W. Opitz, +Sandra Panizza,+Barak A. Pearlmutter,-Ed Pednault,+Jing Peng,+Fernando Pereira, +Aurora Perez,+Bernhard Pfahringer,+David Pierce,-Krishnan Pillaipakkamnatt,+Roberto Piola,+Leonard Pitt,+Lorien Y. Pratt,-Armand Prieditis,+Foster J. Provost,-J. R. Quinlan,+John Rachlin,+Vijay Raghavan,-R. Bharat Rao,-Priscilla Rasmussen,+Joel Ratsaby,+Michael Redmond,+Patricia J. Riddle,+Lance Riley,+Ronald L. Rivest,+Huw Roberts,+Dana Ron,+Robert S. Roos,+Justinian Rosca,+John R. Rose,+Dan Roth,+James S. Royer,+Ronitt Rubinfeld,-Stuart Russell, +Lorenza Saitta,+Yoshifumi Sakai,+William Sakas,+Marcos Salganicoff,-Steven Salzberg,-Claude Sammut,+Cullen Schaffer,+Robert Schapire,+Mark Schwabacher, +Michele Sebag,+Gary M. Selzer, +Sebastian Seung,-Arun Sharma,+Jude Shavlik v ,+Daniel L. Silver,-Glenn Silverstein,+Yoram Singer,+Mona Singh,+Satinder Pal Singh,+Kimmen Sjolander,+David B. Skalak,+Sean Slattery,+Robert Sloan, +Donna Slonim,+Carl H. Smith,+Sonya Snedecor,+Von-Wun Soo,-Thomas G. Spalthoff,+Mark Staley,-Frank Stephan,+Mandayam T. Suraj,+Richard S. Sutton, +Joe Suzuki,-Prasad Tadepalli,+Hiroshi Tanaka,-Irina Tchoumatchenko,-Brian Tester,-Chen K. Tham,+Tatsuo Unemi,-Lyle H. Ungar,+Paul Utgoff,+Karsten Verbeurgt ,+Paul Vitanyi,+Xuemei Wang,+Manfred Warmuth,+Gary Weiss,-Sholom Weiss, -Thomas Wengerek,-Bradley L. Whitehall,-Alma Whitten,+Robert Williamson, +Janusz Wnek,+Kenji Yamanishi,+Takefumi Yamazaki,+Holly Yanco,+John M. Zelle ,-Thomas Zeugmann,+Jean-Daniel Zucker,+Darko Zupanic;for(int m=1;m8;m+)for(int i=0;i280;i+) if(namei0=+)if(count=0)lettercount=nameim;count+;continue;/判断读取的字母是否已存入letter数组for(int j=0;jcount;j+)if(nameim=letterj)flag+;/如果已存入则给flag加1/如果flag等于0，则该字母还未被存入if(flag=0)lettercount=nameim;/存入count+;flag=0;/初始化flagcout发“+”徽章的人名字的第m个字符：;for(int k=0;k64&(int)letterk74)cout0(int)letterk-647