大学生数学建模竞赛论文用分类法基于VC++6.0解决徽章问题

本科生学科大赛

2014数学建模竞赛承诺书我们仔细阅读了河西学院大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B参赛队员(打印并签名)：序号姓名(打印)所在学院签名123指导教师或指导教师组负责人(打印并签名)：日期：2014年05评阅编号（由竞赛组委会评阅前进行编号）：大学生学科大赛

2014年数学建模竞赛评阅专用页评阅编号（由竞赛组委会评阅前进行编号）：评阅记录（供竞赛组委会评阅时使用）：评阅人评分备注评阅结果：获奖等级：用分类法基于VC++6.0解决徽章问题摘要：判别分析是用于判别个体所属群体的一种多元统计分析方法。产生于30年代，近年来在多个学科中都有广泛应用。其特点便是根据已掌握的数据信息，总结出客观事物分类的规律，建立判别公式或判别准则，然后新的样本点根据所建立的判别准则就可以知道它属于哪一类。而本题中的问题是对“机器学习与计算学习理论”的国际会议上参加会议的280名代表收到会议组织者发给的一枚徽章的分类问题（徽章的标记为“＋”或“－”，且每位代表得到徽章“＋”或“－”的标记只与他们的姓名有关）。所以该问题可以用判别分析法建立数学模型进行求解。问题一：首先采用观察法大致的判断出徽章的分类与姓名的单个字母有关，对此我们可以作出假设：徽章分类与姓名中的单个字母有关，运用判别分析法建立数学模型，采用统计的方式运用VC++6.0对数据（姓名中的单个字母）进行统计分类。就会发现其中的规律：参加会议的代表的徽章的分类方法与会议人员姓名中的第二个英文字母是否为元音()有关。问题二：在问题一的基础上，通过附表1中所给出的数据对问题一进行验证分析，便可以知道问题一中所得出的结论在该题目中给的有限数据内是完全正确的。问题三：由于已验证所得的结论是完全正确的，所以问题三可以利用问题二中的检验程序（附录程序3）判断出没能参加会议的14名代表徽章分配的方法，得出只有姓名是AttilioGiordana的徽章为“-”，而其他所有代表的徽章全部是“+”。关键字：判别分析法，多元统计分析，观察法，统计，VC++6.0，元音()一、问题的重述问题背景：在1994年的“机器学习与计算学习理论”的国际会议上，参加会议的280名代表都收到会议组织者发给的一枚徽章，徽章的标记为“＋”或“－”（参加会议的名单及得到的徽章见附表）。会议的组织者声明：每位代表得到徽章“＋”或“－”的标记只与他们的姓名有关，并希望代表们能够找出徽章“＋”与“－”的分类方法。需解决的问题：1.请你帮助参加会议的代表找出徽章的分类方法；2.对你的分类方法进行分析，如分类的理由、分类的正确与错误率等；3.由于客观原因，有14名代表（见附表）没能参加此次会议。按照你的方法，如果他们参加会议，他们将得到什么类型的徽章？二、问题分析（一）问题一的分析：由于题目给出徽章的“+”“－”标记只与每位代表的姓名有关，因此可以猜想徽章的分类方法：1、与组成姓名的字母个数的奇偶性有关；2、与姓名中的某一单个字母有关；3、与姓氏的排列有关。根据观察法可以得出徽章的分类与组成姓名的字母个数的奇偶性、姓氏的排列无关，因此我们猜想徽章分类与姓名中的字母有关。由于以上原因，我们可以建立一个数学模型：依次找出姓名中的单个字母，进行筛选统计，运用判别分析法找出规律，证明猜想。（二）问题二的分析：根据找出的分类方法，运用建立的数学模型，随机的在附表1中找出姓名进行验证并统计结果，对比附表1来分析验证数学模型的正确性以及使用该模型的错误率。（三）问题三的分析：问题3要求对没能参加会议的14名代表进行徽章分配，所以可以在VC++6.0的环境下利用程序进行徽章分配。三、模型假设与符号说明（一）模型假设：1、假设附表1中所给的数据都准确；2、假设每个姓名中所含的英文字母个数全部为50，如果不够则自动添加空格使其达到50个；3、假设所给姓名中全为规范英文名；4、假设徽章的分配方式与姓名中出现的“.”无关。（二）符号说明：1、附表1、附表2、附表3、附表4、程序（1）、程序（2）、程序（3）见附录；2、在整个过程中区分英文字母的大小写；3、程序（1）与程序（3）中“str[50]”表示“附表1中其中一个代表的姓名（其中50指‘假设中的姓名所含字母个数不超过50’）”4、程序（2）中：符号s1s2s3s4s5s6s7代表该字母个数aoeiuyr符号s8s9s10s11s12s13s14代表该字母个数hvnltcs符号s15s16s17s18s19s20s21代表该字母个数mfdATRJ符号s22代表该字母个数B注：根据程序（1）中的数据统计，上表包含了姓名中的第二个英文字母出现所有情形。四、模型建立与求解问题一：参加会议代表徽章的分类方法：本题目中给出了参加会议的280名人员名单以及所得到的徽章的标记，让得出分类方法并且判断出未参加会议的14名代表的徽章标记。这种问题刚好可以运用判别分析法来解决。该方法可以根据已知准确的徽章分配数据信息，总结出徽章分配的规律，建立判别准则，然后未参加会议的14名代表便可以根据所建立的判别准则来判断他们该分配哪种标记的徽章。而对于程序编写来说，C语言具有功能丰富、表达能力强、使用灵活方便、应用面广、目标程序效率高等其他诸多优点。它作为传统的面向过程的程序设计语言，更适合解决小型程序的编程。因此下面我们用判别分析法通过VC++6.0编程来建立数学模型解决问题：数学模型的建立：1、根据附表1可看出徽章的分类与姓名首字母（姓名排列）之间毫无规律可言，如：+AaronFeigelson、-AmeurFoued、-AntoineCornuejols、+AuroraPerez四个姓名中有“+”有“-”。也可以得出同为“+”徽章时，组成姓名的英文字母奇偶不相同，因此得出徽章的分类方法与组成姓名字母的奇偶性无关；2、通过对数据的分析，进一步可以得出徽章分类与姓也没有关系，如：+Pang-ChiehChen、-ZhixiangChen中姓相同，但所得到的徽章也不相同；3、从姓名的第二个字母开始由于问题给出的名字实在太多，排列顺序比较混乱，所以先要对这些名字以及他们所对应的徽章符号进行统计。将附表1重新按“+”“-”整理得出附表3，经统计：得"+"的名字有197个，得"-"的名字有83个。然后可以建立数学模型：将280个人中的每一个人的姓名都看成一个集合并加以编号，为()。把每个集合中相对应的元素比较总结并一一归纳，便可以得出集合中第二个元素是中的一个时，该人员所的徽章为“+”，而集合中的第二个元素是中的一个时所得徽章为“-”。也即判别准则为：①当集合()中的第二个元素时，得到“+”徽章；②当集合()中的第二个元素时，得到“-”徽章。通过VC++6.0运行程序（1）得出每个姓名中的第二个英文字母，然后将所得出的所有英文字母在VC++6.0的环境下输入到程序（2）(以“#”结束运行)运行，把所显示数据整理统计得出姓名中的第二个字母以及其出现次数的统计表格，即附表4。根据附表4，可以得出参加会议得到“+”徽章的人员的姓名第二个英文字母是元音（a,o,e,i,u）中其中的一个，否则会议人员得到“-”徽章。也即：参加会议的代表的徽章分类方法为如果会议人员姓名中的第二个英文字母是元音（a,o,e,i,u）中的一个，就会得到“+”徽章，否则则得到“-”徽章。问题二：分类方法分析：（一）分类的理由：英文名字之间的规律与组成它的各个字母密切相关（观察法），在附表1中找出2组数据：第一组：+Pang-ChiehChen-ZhixiangChen第二组：+DavidHaussler+DavidHelmbold由这两组数据可以得知分类方法与名有关而与姓无关，再在附表1中找其他数据（如：+NaokiAbe、-MyriamAbramson、-ChidanandApte、+MinoruAsada等），通过对数据的分析：第一个单词的长短、字母个数的奇偶，字母是否为元音（或辅音）等可以得出以上的分类方法。（二）分类的正确与错误率：由于该结论是由题目中给出的全部数据总结所得，所以完全正确。问题三：由于客观原因而没能参加此次会议的14名代表（见附表2），如果他们参加会议，则运用程序（3）将未参加的14名代表姓名依次输入程序并运行，便可得该14名代表的名单及得到的徽章：+MerrickL.Furst+JeanGabrielGanascia+WilliamGasarch+RicardGavalda+MelindaT.Gervasio+YolandaGil+DavidGillman-AttilioGiordana+KateGoelz+PaulW.Goldberg+SallyGoldman+DianaGordon+GeoffreyGordon+JonathanGratchVC++6.0程序运行流程图：（流程图中的程序详见附录）五、模型检验将附表1中所有的姓名全部带入模型中进行验证，再将所得徽章的结果与附表1中数据进行比较。结果显示，完全正确。模型检验正确无误。六、模型的改进1、对模型中的程序进行改进，使其能一次性输入大量原数据进行处理、统计；2、尝试在其他环境下编写程序，使其能够直接复制粘贴原数据，减少人为输入原数据时产生的错误；3、改进程序，让其能够在输入姓名后能直接统计出姓名中第二个字母的个数，并能够在输入错误或少（或多）输入姓名时能提示且在原来的基础上重新输入。七、模型的优缺点模型优点：1、所建立的模型是以较为简单的C语言程序及统计方面的知识为基础，简单易懂，准确性高；2、在本题中能够简单准确的进行徽章的分类；3、对于少量数据的处理来说，该模型的处理比较简洁方便；4、该模型具有较强的规律性，思路明确简单。模型缺点：1、VC++6.0运行时不能对数据进行复制粘贴，因此导致检验模型繁琐，耗时太多，效率极低；2、给程序中输入数据时必须不能出现错误，否则整个运行结果将会出错；3、模型中只考虑了部分因素，有很大的局限性；4、由于所得的结论是由本题中的数据统计得出的，数据量较少，结论具有偶然性；5、该模型只能用于少量数据的处理，对于大量数据具有极大限制性。八、参考文献：[1]谭浩强《C程序设计》清华大学出版社（2013年2月）[2]河西学院数学建模竞赛论文word模板[3]上传者：whywhatwhenhow(百度文库)《数学建模算法全收录pdf》网址:/download/whywhatwhenhow/2035100(2014年5月24日）[4]上传者：wpinghui1(百度文库)《如何撰写数学建模论文》网址:/view/f770990879563c1ec5da71c8.html(2014年5月24日）[5]韩中庚《数学建模竞赛——获奖论文精选与点评（第1版）》科学出版社(2008年4月7日)九、附录附表１：参加会议的名单及得到的徽章+NaokiAbe-MyriamAbramson+DavidW.Aha+KamalM.Ali-EricAllender+DanaAngluin-ChidanandApte+MinoruAsada+LarsAsker+JavedAslam+HaralabosAthanassiou+JoseL.Balcazar+TimothyP.Barber+MichaelW.Barley-CristinaBaroglio+PeterBartlett-EricBaum+WeltonBecket-ShaiBen-David+GeorgeBerg+NeilBerkman+MaliniBhandaru+BirBhanu+ReinhardBlasig-AvrimBlum-AnselmBlumer+JustinBoyan+CarlaE.Brodley+NaderBshouty-WrayBuntine-AndreyBurago+TomBylander+BillByrne-ClaireCardie+RichardA.Caruana+JohnCase+JasonCatlett+NicoloCesa-Bianchi-PhilipChan+MarkChangizi+Pang-ChiehChen-ZhixiangChen+WanP.Chiang-SteveA.Chien+JefferyClouse+WilliamCohen+DavidCohn-ClareBatesCongdon-AntoineCornuejols+MarkW.Craven+RobertP.Daley+LindleyDarden-ChrisDarken-BhaskarDasgupta-BrianD.Davidson+MichaeldelaMaza-OlivierDeVel-ScottE.Decatur+GeraldF.DeJong+KanDeng-ThomasG.Dietterich+MichaelJ.Donahue+GeorgeA.Drastal+HarrisDrucker-ChrisDrummond+HalDuncan-ThomasEllman+TapioElomaa+SusanL.Epstein+BobEvans-ClaudioFacchinetti+TomFawcett-UsamaFayyad+AaronFeigelson+NicolasFiechter+DavidFinton+JohnFischer+PaulFischer+SethFlanders+LanceFortnow-AmeurFoued+JudyA.Franklin+YoavFreund+JohannesFurnkranz+LeslieGrate+WilliamA.Greene+RussellGreiner+MarkoGrobelnik+TalGrossman+MargoGuertin+TomHancock+EarlS.HarrisJr.+DavidHaussler+MatthiasHeger+LisaHellerstein+DavidHelmbold+DanielHennessy+HaymHirsh+JonathanHodgson+RobertC.Holte+JiarongHong-Chun-NanHsu+KazushiIkeda+MasayukiInaba-DragoIndjic+NitinIndurkhya+JeffJackson+SanjayJain+WolfgangJanko-KlausP.Jantke+NathalieJapkowicz+GeorgeH.John+RandolphJones+MichaelI.Jordan+LesliePackKaelbling+BalaKalyanasundaram-ThomasE.Kammeyer-GrigorisKarakoulas+MichaelKearns+NeelaKhan+RoniKhardon+DennisF.Kibler+Jorg-UweKietz-EfimKinber-JyrkiKivinen-EmanuelKnill-CraigKnoblock+RonKohavi+PascalKoiran+MosheKoppel+DanielKortenkamp+MatevzKovacic-StefanKramer+MartinchKrikis+MartinKummer-EyalKushilevitz-StephenKwek+WaiLam+KenLang-SteffenLange+PatLangley+MarySoonLee+WeeSunLee+MosheLeshno+Long-JiLin-CharlesX.Ling+MichaelLittman+DavidLoewenstern-PhilLong+WolfgangMaass-BruceA.MacDonald+RichMaclin-SridharMahadevan-J.JeffreyMahoney+YishayMansour+MarioMarchand-ShaulMarkovitch-OdedMaron+MajaMataric+DavidMathias+ToshiyasuMatsushima-StanMatwin-EddyMayoraz-R.AndrewMcCallum-L.ThorneMcCarty-AlexanderM.Meystel+MichaelA.Meystel-StevenMinton+NinaMishra+TomM.Mitchell+DunjaMladenic+DavidMontgomery-AndrewW.Moore+JohanneMorin+HiroshiMotoda-StephenMuggleton+PatrickM.Murphy-SreeramaK.Murthy+FilippoNeri-CraigNevill-Manning-AndrewY.Ng+NikolayNikolaev-StevenW.Norton+JosephO'Sullivan+DanOblinger+Jong-HoonOh-ArlindoOliveira+DavidW.Opitz+SandraPanizza+BarakA.Pearlmutter-EdPednault+JingPeng+FernandoPereira+AuroraPerez+BernhardPfahringer+DavidPierce-KrishnanPillaipakkamnatt+RobertoPiola+LeonardPitt+LorienY.Pratt-ArmandPrieditis+FosterJ.Provost-J.R.Quinlan+JohnRachlin+VijayRaghavan-R.BharatRao-PriscillaRasmussen+JoelRatsaby+MichaelRedmond+PatriciaJ.Riddle+LanceRiley+RonaldL.Rivest+HuwRoberts+DanaRon+RobertS.Roos+JustinianRosca+JohnR.Rose+DanRoth+JamesS.Royer+RonittRubinfeld-StuartRussell+LorenzaSaitta+YoshifumiSakai+WilliamSakas+MarcosSalganicoff-StevenSalzberg-ClaudeSammut+CullenSchaffer+RobertSchapire+MarkSchwabacher+MicheleSebag+GaryM.Selzer+SebastianSeung-ArunSharma+JudeShavlik+DanielL.Silver-GlennSilverstein+YoramSinger+MonaSingh+SatinderPalSingh+KimmenSjolander+DavidB.Skalak+SeanSlattery+RobertSloan+DonnaSlonim+CarlH.Smith+SonyaSnedecor+Von-WunSoo-ThomasG.Spalthoff+MarkStaley-FrankStephan+MandayamT.Suraj+RichardS.Sutton+JoeSuzuki-PrasadTadepalli+HiroshiTanaka-IrinaTchoumatchenko-BrianTester-ChenK.Tham+TatsuoUnemi-LyleH.Ungar+PaulUtgoff+KarstenVerbeurgt+PaulVitanyi+XuemeiWang+ManfredWarmuth+GaryWeiss-SholomWeiss-ThomasWengerek-BradleyL.Whitehall-AlmaWhitten+RobertWilliamson+JanuszWnek+KenjiYamanishi+TakefumiYamazaki+HollyYanco+JohnM.Zelle-ThomasZeugmann+Jean-DanielZucker+DarkoZupanic附表2：没能参加此次会议的名单MerrickL.FurstJeanGabrielGanasciaWilliamGasarchRicardGavaldaMelindaT.GervasioYolandaGilDavidGillmanAttilioGiordanaKateGoelzPaulW.GoldbergSallyGoldmanDianaGordonGeoffreyGordonJonathanGratch附表3：将参加会议的人员按所得徽章的正负重新处理：徽章为“+”：+NaokiAbe+DavidW.Aha+KamalM.Ali+DanaAngluin+MinoruAsada+LarsAsker+JavedAslam+HaralabosAthanassiou+JoseL.Balcazar+TimothyP.Barber+MichaelW.Barley+PeterBartlett+WeltonBecket+GeorgeBerg+NeilBerkman+MaliniBhandaru+BirBhanu+ReinhardBlasig+JustinBoyan+CarlaE.Brodley+NaderBshouty+TomBylander+BillByrne+RichardA.Caruana+JohnCase+JasonCatlett+NicoloCesa-Bianchi+MarkChangizi+Pang-ChiehChen+WanP.Chiang+JefferyClouse+WilliamCohen+DavidCohn+MarkW.Craven+RobertP.Daley+LindleyDarden+MichaeldelaMaza+GeraldF.DeJong+KanDeng+MichaelJ.Donahue+GeorgeA.Drastal+HarrisDrucker+HalDuncan+TapioElomaa+SusanL.Epstein+BobEvans+TomFawcett+AaronFeigelson+NicolasFiechter+DavidFinton+JohnFischer+PaulFischer+SethFlanders+LanceFortnow+JudyA.Franklin+YoavFreund+JohannesFurnkranz+LeslieGrate+WilliamA.Greene+RussellGreiner+MarkoGrobelnik+TalGrossman+MargoGuertin+TomHancock+EarlS.HarrisJr.+DavidHaussler+MatthiasHeger+LisaHellerstein+DavidHelmbold+DanielHennessy+HaymHirsh+JonathanHodgson+RobertC.Holte+JiarongHong+KazushiIkeda+MasayukiInaba+NitinIndurkhya+JeffJackson+SanjayJain+WolfgangJanko+NathalieJapkowicz+GeorgeH.John+RandolphJones+MichaelI.Jordan+LesliePackKaelbling+BalaKalyanasundaram+MichaelKearns+NeelaKhan+RoniKhardon+DennisF.Kibler+Jorg-UweKietz+RonKohavi+PascalKoiran+MosheKoppel+DanielKortenkamp+MatevzKovacic+MartinchKrikis+MartinKummer+WaiLam+KenLang+PatLangley+MarySoonLee+WeeSunLee+MosheLeshno+Long-JiLin+MichaelLittman+DavidLoewenstern+WolfgangMaass+RichMaclin+YishayMansour+MarioMarchand+MajaMataric+DavidMathias+ToshiyasuMatsushima+MichaelA.Meystel+NinaMishra+TomM.Mitchell+DunjaMladenic+DavidMontgomery+JohanneMorin+HiroshiMotoda+PatrickM.Murphy+FilippoNeri+NikolayNikolaev+JosephO'Sullivan+DanOblinger+Jong-HoonOh+DavidW.Opitz+SandraPanizza+BarakA.Pearlmutter+JingPeng+FernandoPereira+AuroraPerez+BernhardPfahringer+DavidPierce+RobertoPiola+LeonardPitt+LorienY.Pratt+FosterJ.Provost+JohnRachlin+VijayRaghavan+JoelRatsaby+MichaelRedmond+PatriciaJ.Riddle+LanceRiley+RonaldL.Rivest+HuwRoberts+DanaRon+RobertS.Roos+JustinianRosca+JohnR.Rose+DanRoth+JamesS.Royer+RonittRubinfeld+LorenzaSaitta+YoshifumiSakai+WilliamSakas+MarcosSalganicoff+CullenSchaffer+RobertSchapire+MarkSchwabacher+MicheleSebag+GaryM.Selzer+SebastianSeung+JudeShavlik+DanielL.Silver+YoramSinger+MonaSingh+SatinderPalSingh+KimmenSjolander+DavidB.Skalak+SeanSlattery+RobertSloan+DonnaSlonim+CarlH.Smith+SonyaSnedecor+Von-WunSoo+MarkStaley+MandayamT.Suraj+RichardS.Sutton+JoeSuzuki+HiroshiTanaka+TatsuoUnemi+PaulUtgoff+KarstenVerbeurgt+PaulVitanyi+XuemeiWang+ManfredWarmuth+GaryWeiss+RobertWilliamson+JanuszWnek+KenjiYamanishi+TakefumiYamazaki+HollyYanco+JohnM.Zelle+Jean-DanielZucker+DarkoZupanic徽章为“-”：-MyriamAbramson-EricAllender-ChidanandApte-CristinaBaroglio-EricBaum-ShaiBen-David-AvrimBlum-AnselmBlumer-WrayBuntine-AndreyBurago-ClaireCardie-PhilipChan-ZhixiangChen-SteveA.Chien-ClareBatesCongdon-AntoineCornuejols-ChrisDarken-BhaskarDasgupta-BrianD.Davidson-OlivierDeVel-ScottE.Decatur-ThomasG.Dietterich-ChrisDrummond-ThomasEllman-ClaudioFacchinetti-UsamaFayyad-AmeurFoued-Chun-NanHsu-DragoIndjic-KlausP.Jantke-ThomasE.Kammeyer-GrigorisKarakoulas-EfimKinber-JyrkiKivinen-EmanuelKnill-CraigKnoblock-StefanKramer-EyalKushilevitz-StephenKwek-SteffenLange-CharlesX.Ling-PhilLong-BruceA.MacDonald-SridharMahadevan-J.JeffreyMahoney-ShaulMarkovitch-OdedMaron-StanMatwin-EddyMayoraz-R.AndrewMcCallum-L.ThorneMcCarty-AlexanderM.Meystel-StevenMinton-Andrew