威尼斯人娱乐全部考试的学识都属于选考科目考试正式的范围,以为程序算法依旧挺风趣的

考题来源:http://student.csdn.net/mcs/programming_challenges?&page=1
 观察FIFA World Cup

威尼斯人娱乐 1

  

有奖考查:高三今年得花多少钱

  以往在这个学院参与每年的ACM程序设计大赛,感到程序算法依然相当好玩的,这两日开掘三个网址上释放部分算法试题,有一点当年的这种心境,看到了,感到能杀死,那就干掉它。如今还在商店守夜中,闲着没事就试了试算法题。

双五星级 名单你读懂了吗 为什么分成AB类

  速手打,未有详细检查,也许有短处请见谅,可是读题、解题、算法设计,多少个众多。

高三家长必需精晓的9条自己作主招收政策

 if(type == 1){...} 这段里,虽然写的有点小复杂,但是是个简单的优化,呵呵。

自己作主招生 与自招相关的比赛 专家建议自招早做策动

  做事前,先看清,再入手。程序员时间有限,不要轻便浪费,错误的解读,终会招致贰个不得法的结果。

解密专门的职业19期:神秘的中军事学

class Program
    {
        /*
         *     世界杯正在火热进行中,室友不惜睡眠时间,凌晨起来观看,但Njzy对此不是很感兴趣,他在思考一个问题: 
         * 假设世界杯观看台上有n个座位,排成一排,游客们来到这里自由占位。一般情况下,一个游客首先考虑的座位
         * 肯定是两边都没人的座位,其次考虑的是一边没人的座位,最后没得考虑,只能随便选一张两边都是人的座位。
         * 假设有n个游客依次到场占位,每个人都是按照上述规则选择自己的位子,Njzy就在思考这n个游客占位的可能顺
         * 序有多少种,你能帮助他? 输入描述: 有多组测试数据,每组测试数据包括一个正整数n(0<n<1000000)。 输出
         * 描述: 对于每组数据,由于答案可能会很大,所以输出:答案%1000000007
         * 
         * **************************************
         * 
         * 首先仔细读题:
         *  1.世界杯观看台上有n个座位,这n个座位有n个依次到场的游客来坐。
         *    解析:这里面隐藏两点(这两点很重要,如果没有读出这两点,计算会非常复杂):
         *                  a.座位数等于游客数
         *                  b.游客有入场顺序(此题中游客的入场顺序为1,2,3,4...)
         * (限制型排序算法)                 
         * 
         *                  
         *  2.首先考虑的座位肯定是两边都没人
         *  
         *  3.其次考虑的是一边没人的座位
         *  
         *  4.只能随便选一张两边都是人的座位
         *  
         * 
         * 输出结果:
         * 表示游客的选座方法(顺序号对应游客的入场顺序)。
         * 
         * 
         * 修改 _PersonCount 的值表示入场的人数(座数),为题中n(0<n<1000000)
         * 如果只求出总选座的方法,可以注释 Console.WriteLine(string.Join(",", _SiteArray));
         * 没有输出,提高程序的计算效率。
         */

        static void Main(string[] args)
        {
            //假设:人数、座位数(1,2,3...表示游客的入场顺序)
            int _PersonCount = 4;

            int[] _SiteArray = new int[_PersonCount];

            int personIndex = 1;
            int type = 2;

            switch (_SiteArray.Length)
            {
                case 0: type = -1; break;
                case 1: type = 0; break;
                case 2: type = 1; break;
                case 3: type = 2; break;
                default: type = 2; break;
            }

            FuncRun(ref _SiteArray, ref personIndex,  type);

            Console.WriteLine("总共 {0} 种选座的方法",ResCount);
        }

        static void Swap(ref int l, ref int r)
        {
            l = l ^ r;
            r = l ^ r;
            l = l ^ r;
        }

        static int ResCount = 0;

        static void FuncRun(ref int[] _SiteArray, ref int personIndex,  int type)
        {
            if (personIndex > _SiteArray.Length)
            {
                Console.WriteLine(string.Join(",", _SiteArray));
                ResCount++;
                return;
            }

            if (type == 2)
            {
                //---------------------------------------------------
                //首先考虑的座位肯定是两边都没人
                for (int i = 1; i < _SiteArray.Length - 1; i++)
                {
                    if (_SiteArray[i] > 0)
                        continue;

                    if (_SiteArray[i - 1] == 0 && _SiteArray[i + 1] == 0)
                    {
                        _SiteArray[i] = personIndex++;
                        FuncRun(ref _SiteArray, ref personIndex,  type);
                        //数据恢复
                        personIndex--;
                        _SiteArray[i] = 0;
                    }
                }
                type--;
            }

            //---------------------------------------------------
            //其次考虑的是一边没人的座位
            if (type == 1)
            {
                if (personIndex <= 1 || _SiteArray.Length < 3)
                    return;

                if (_SiteArray[0] == 0 && _SiteArray[1] == 0)
                {
                    _SiteArray[0] = personIndex++;
                    FuncRun(ref _SiteArray, ref personIndex,  type);
                    //数据恢复
                    personIndex--;
                    _SiteArray[0] = 0;
                }

                for (int i = 1; i < _SiteArray.Length - 1; i++)
                {
                    if (_SiteArray[i] > 0)
                        continue;

                    if (_SiteArray[i - 1] == 0)
                    {
                        _SiteArray[i] = personIndex++;
                        FuncRun(ref _SiteArray, ref personIndex,  type);
                        //数据恢复
                        personIndex--;
                        _SiteArray[i] = 0;
                    }
                    else if (_SiteArray[i + 1] == 0)
                    {
                        _SiteArray[i] = personIndex++;
                        FuncRun(ref _SiteArray, ref personIndex,  type);
                        //数据恢复
                        personIndex--;
                        _SiteArray[i] = 0;
                    }
                }

                if (_SiteArray[_SiteArray.Length - 1] == 0 && _SiteArray[_SiteArray.Length - 2] == 0)
                {
                    _SiteArray[_SiteArray.Length - 1] = personIndex++;
                    FuncRun(ref _SiteArray, ref personIndex,  type);
                    //数据恢复
                    personIndex--;
                    _SiteArray[_SiteArray.Length - 1] = 0;
                }
                type--;
            }

            //---------------------------------------------------
            //只能随便选一张两边都是人的座位
            if (type == 0)
            {
                for (int i = 0; i < _SiteArray.Length; i++)
                {
                    if (_SiteArray[i] == 0)
                    {
                        _SiteArray[i] = personIndex++;
                        FuncRun(ref _SiteArray, ref personIndex,  type);
                        //数据恢复
                        personIndex--;
                        _SiteArray[i] = 0;
                    }
                }
            }
        }
    }

解密专门的学业 聪明的男女学物理 经济学

纵观各次音讯才能选考,全数加试题从知识内容上说都未有当先考试正式的局面。但此前两遍选考加试题得分意况来看,考生的得分率普及不是相当高。回想前两回选考,看看加试题考什么、怎么考,只怕能得到部分新启示。

威尼斯人娱乐 2

考什么

所谓“知己知彼,战无不胜”,要在选考中发挥出较好的水平,必需求分明地握住选考内容。

纵观前两回选考,加试题总分为15分,由3个采取题(第10、11、12题,共6分)和2个非接纳题(第16、17题,共9分)组成。从知识点布满来看,首要集聚在“多媒体音讯编码”、“算法与VB程序设计”。除了那么些之外,为了考试学生疏析化解难点的力量,每趟试验的末尾一题(第17题)都会出现贰个综合题,此类综合题不局限于有个别优秀算法,往往综合采纳了程序设计中的各样艺术与技艺,大家得以称作“开放性试题”。

尤其剖析,“算法与VB程序设计”主要考察了排序、查找、自定义函数、字符串管理等算法与知识。而If语句、循环语句及数组、常见对象属性操作等编制程序基础知识,差非常少渗透到了各样试题。

威尼斯人娱乐 3

怎么考

根据上述梳理可见,全体考试的学识都属于选考科目考察正式的层面。但出于试题的样式以及考试切入点的新颖性,会给考生一种不鲜明感,总体来讲那三回选考试题展现出下列特征。

1。 守旧题讲究周详而透顶

这里的观念意识题指的是主题素材熟知、所需知识与求解目的以内关系较为直接的试题,如表1所示的4个关于多媒体音信编码的考题。

那类试题的风味是供给考生全面地了然相关的基础知识,并能直接动用那个知识求解试题。如二〇一四年15月选考的第10题:

[加试题]将贰个时长为1秒钟、采集样品频率为44.1kHz、量化位数为16、双声道未经压缩的Wave格式音频文件压缩为MP4格式文件,压缩后的VCD格式文件大小为940KB,则其缩减比约为

A、 11:1 B、 11:2 C、 11:4 D、 88:1

考生首先要通晓音频数据数字化的法规,然后结合音频采集样品特点,总计出该音频未经压缩的存款和储蓄量为10335.9375KB,将此结果除以减掉后的寄存体积就可以获得削减比约为11∶1(选项A)。

再如2015年3月、2016年11月的第10题都以本着BMP图像数字化及存储量总结的考察,固然知识点同样,但考试的切入点分歧。后边三个须求考生依据分辨率和每种像素存款和储蓄所需的二进制位数总结图像的存款和储蓄量,而后人供给考生依照存款和储蓄量和分辨率反向计算每一个像素存款和储蓄所需的二进制位数。

威尼斯人娱乐 4

 

有奖考察:高三那年得花多少钱

双五星级 名单你读懂了吗 为啥分成AB类

高三家长必需了然的9条自己作主招生政策

自主招生 与自招相关的竞技 专家提出自招早做计划

解密专门的学问19期:神秘的中管历史学

解密专门的学问 聪明的子女学物理 艺术学

2、 算法题重视考察算法原理和策画观念

学习算法与程序设计不仅仅要会沿用杰出算法的次第框架来消除实际难点,更要在浓厚了然算法原理的基础上,慢慢产生基于既有算法改变之上的算法设计技艺。加试部分的算法与程序设计题,充裕呈现了这种价值取向。

如二〇一六年6月的第16题,要求考生在领略古板冒泡排序算法基础上,依照试题提醒解析原算法中存在的冗余管理,并遵照革新后的算法要求考订程序中的错误。宗旨部分的程序段如下:

威尼斯人娱乐 5

主题考查的首要特征为:

知情冒泡排序算法的原理

冒泡排序的基本原理是历次在三个未管理区间内扫描,发现逆序对数码后即实行交流,慢慢压缩扫描区间直到区间长度为2。该算法的创新原理正是当剩余区间内数据尚未发觉逆序对时,就能够甘休排序。假诺考生对原冒泡排序算法的规律领悟非常不足深入,就不能够设计出相应的巡回条件并达成改错。

略知一二冒泡排序程序外循环循环变量的职能原理

读本中冒泡排序算法用For i=1 to
n-1语句来决定外循环,循环变量i的根本意义有多少个,一是冒泡排序加工的遍数,二是为每遍的加工设定左侧界。借使考生不能够对那些规律有深远的知晓,就不可能知晓外循环变量i的机能,也就无法准确深入分析出Do
While循环语句中的条件进而准确写出改良后的结果(将标识(1)处的“or”改为“and”、将符号(2)处的“i”改为“i-1”)。

再如二〇一四年10月第11、12题,二〇一七年十月第11题,二〇一七年十一月第12题。那一个课题首先需求使用已学习成绩非凡良算法的法规去明白新的程序,更要基于新的难题去创造性地设总括法消除难点。以二零一七年14月的第12题为例,试题要求考生使用已学的接纳排序算法观念,完善立异后的在两个同期开展抉择的排序程序。该题的非常重要内容如下:

威尼斯人娱乐 6威尼斯人娱乐 7

该题的试验特点有:

应用内化的接纳排序观念理解新的取舍排序算法

主旨能够说是考试选择排序算法,但又不囿于于调查教材中的接纳排序算法,而是必要接纳内化的采取排序中的“选取”思想,去支持领悟立异后的新排序算法。

依据新主题材料特点去创立性地设总括法

改进后的抉择排序算法带来了新的标题,即两侧同时进行精选时所推动的数据调换的相互影响。为了化解这一个新主题素材,供给考生能凭仗标题特点去完善算法(设计观念)。新题材唯有在左端点是最大值时发出,抱蔓摘瓜实行深入分析,当最小值被换到到左端点时,最大值被换到到iMin所指地方,所以正确选拔为A。
威尼斯人娱乐 8

有奖考查:高三那年得花多少钱

双顶尖 名单你读懂了吗 为什么分成AB类

高三家长必得精通的9条自己作主招收政策

自主招生 与自招相关的比赛 专家提议自招早做盘算

解密专门的学业19期:神秘的中管工学

解密职业 聪明的儿女学物理 艺术学

3、 开放性试题重申整决难题

为了考试学生设计算法消除难点的力量,三遍选考都冒出了开放性试题。此类试题的风味是一向不非凡算法的阴影,考生在深入分析程序时力不胜任依照有些优异算法的框架来支援深入分析、设总计法,目标是考试学生疏析难点、创建性地设总括法化解难题的技能。

此间的算法设计不是从零发端的安顿,而是依照试题给出的任务和算法管理特点,针对程序中的断层(须求改错或许补充)设总结法。如,二零一四年五月的第17题空格②(核心代码段如下)。

威尼斯人娱乐 9

依靠试题给出的数码加密方法以及自定义函数Code2Char()的作用,考生如能设计出“收取字符串s中第c+1个字符,并将该字符通过函数再次回到”的算法,就能够动用字符串函数写出这里应填的代码“Mid(s,c+1,1)”。

怎么学

1、 精通程序设计本质,驾驭首要知识

微型Computer实行自动化数据管理的精神是对具体数据的规律性重复管理,因而前后相继设计的骨干正是抽象数据再度管理的规律,并将规律通进度序再说展现。在那么些进度中,规律性的再次管理往往用循环结构来实现,而数据的法则化组织又通过数组来兑现。因而,循环和数组就产生了前后相继设计中的关键知识。实际前四回选考的拾伍个关于程序设计的加试题中,全体都涉及了循环语句和数组应用。为了真正主宰那个根本知识,教学中得以经过变式应用来深化对那么些知识的明亮和摆布,如原本用For语句完毕的巡回结构可思量用Do
While语句来促成,原本用八个数组达成的程序考虑用贰个数组来达成等。

除却数值管理,Computer管理的非数值数据首要正是字符串,加试题也显示了这一个特点(前四回选考17个程序设计题中出现了3题)。为了通晓驾驭字符串管理的第一知识,经常教学中不能只逗留在价值观的字符串表达式计算的规模,而要在各样字符串相关实际难点的消除进度中深远精晓字符串管理技艺,养成字符串管理的开采和思维,不然就便于并发将“Mid(s,c+1,1)”写成“s(c+1)”的错误。能够借鉴的实在难题得以是“字符文本排版”、“身份ID号码校验”等。作为一种发展性思索,教学中还应关注基于字符编码的字符串管理难题的消除。

2、 培育程序设计观念

稍加老师感觉新闻手艺试验是笔试,能够不必实行上机实行,只需坚实笔试题磨练就能够。实际上,从日前试题特征的深入分析可知,就算是笔试题,加试题也早就屏弃了本来“三项试验”中这种通过背代码就能够解题的风骨,而急需在任其自然的主次设计观念援救下本事正确地解题。极度地,为了试验考生的次第设计思想,加试题已经在日趋加强“设计”的分占的额数,而不再是彻彻底底的单个语句的补偿或改错。如二〇一四年13月第11题,考生必要剖判四个语句的咬合顺序,一定水平上还原了程序设计侦察的原型。

前后相继设计观念是当学生面对二个诚实的标题时,在条分缕析难题、设总括法与数据结构、将算法用一种程序设计语言表示并拓宽程序调节和测验的进度中慢慢产生的。这一个进程一再是积重难返、充满波折的,但就是在如此多少个连连试错、反思、调节、感悟的妄图剖释中,程序设计理念能力循环不断演进。只怕一节课学生只调节和测量试验了两个程序,但中间蕴涵了基础知识的回顾与利用、算法的准备与校订、程序代码的剖判等进程,其意思与效率远远超过一节课三番五次讲八个课题。能够从实际中一再开采一些程序设计有关的材质,并经超过实际际编制程序来减轻这一个难点,如超级市场物品出售总计、分享单车使用现状总括等。
威尼斯人娱乐 10

有奖考察:高三那一年得花多少钱

双一级 名单你读懂了吗 为什么分成AB类

高三家长必需精通的9条自主招生政策

自己作主招生 与自招相关的比赛 专家提出自招早做筹划

解密专门的学问19期:神秘的中管医学

解密专门的学问 聪明的子女学物理 工学

3、 针对难题特点,运用深入分析计谋和措施

本着笔试题方式出现的选考,还可提炼并运用一些通用性的顺序分析攻略与艺术,提升解题的科学,如常识战略、黑匣子战略、对应政策等。

常识战术

算法与程序设计中,总存在部分相对稳定的程序完毕方法,总括并选拔那个艺术来支援程序设计和解析就是常识计谋。如:在求和算法中,保存总和的变量一同初总要开始化为零;在求最大值算法中,结果变量最初化值总为贰个一点都不大值只怕第一项数据值;等等。二零一五年十月第16题就可选拔常识计策来求最大值。

黑匣子攻略

黑匣子战术指的是当对某一段程序不可能完全知晓时(该片段程序段能够视作黑匣子),能够先暂且放任该模块内部怎样管理的分析,而只需从已知算法的全部结构出发,深入分析出该模块的效应(即知道该模块在做什么样),并依靠该功用去援救驾驭其余部分的程序代码。那样管理后,一方面可以暂且跳出那几个瓶颈,不致影响对全体难点的求解,另一方面,当其余一些通晓彻底后,反过来又可协助大家对该模块算法的敞亮。

如,在二零一五年3月第17题中,假设第贰遍看程序对于自定义函数Code2Char有一些费解,那么就不要纠结,只需抓住该函数的效应是“将参数c中的整数转变为加密后的字符”,然后采取对该意义的敞亮,进一步深入分析出主程序中Code2Char(b1)和Code2Char(b2)分别在将1个字节的前4位和后4位二进制数对应的编码调换为加密字符。以此为突破口,就会逐步梳理出算法并缓慢解决难题。

威尼斯人娱乐 11

关键变量法

重中之重变量法指的是选择逆向思维,首先鲜明程序输出结果时的要害数据,解析输出结果由哪些变量支配,将那个变量作为根本变量,在解析程序时引发那些首要变量,从珍视变量值的变化规律去归咎程序的拍卖规律,进而稳步梳理出算法并做到解题。

如,二零一五年四月选考的第11题,试题给出三行代码(如下所示),必要分明这三行代码的各样,使得程序(因篇幅有限,别的代码略)能判定s是不是为对称字符串。

在该程序中k是不能缺少变量。结合最后输出语句及第二行代码,可见变量k在总结不一样字符的个数。再组成程序中的其余代码,可进一步逆向测度出变量c1和c2个别表示左右两侧对称地点上的字符。由此可逐渐剖判出不错结合顺序为③②①。

对应政策

对应政策指的是一旦已井然有序的算法观念(能够是温馨归咎得到,也足以是主题材料中提交),那么可在程序中检索算法各种管理步骤对应的言语,然后依照算法须求剖析程序中对应部分的机能并写出所需的代码。

二零一六年十一月选考的第17题即便难度很大,但若是充裕运用对应政策,还能比较顺遂地减轻难题。该题部分代码及难点中对应的点子描述如下表所示。

威尼斯人娱乐 12

循序渐进难题中的方法描述,示例3情景管理时应将a(pa+2)的值重复地赋予寄放解压缩数据的数组b,所以空格②处代码应该为“b(pb+i-1)=a(pa+2)”。而对此空格①处的代码设计,既可对应难点中的方法描述获得,也可经过演示3景观管理中的“pa=pa+3”对应分析得到。

综上可得,加试题重在基本原理领会及应用、新闻本事学科思维的试验,而盲目标题海战术只好徒增师生担当。消息本领教学应顺应大势,着重学科骨干素养、服从试行性和综合性,带领学生在消除实际难点的进度中国和东瀛渐升级消息素养。

正文笔者:吴建峰 高等助教

最早的文章均刊载于《湖南考试》期刊前年第10期

相关文章