零基础学算法课件

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,零基础学算法,第,9,章：信息学奥赛试题精解,课程安排,9.1,NOIP普及组试题精解,9.2 NOIP,提高组试题精解,9.1 NOIP,普及组试题精解,9.1.1,求级数之和,9.1 NOIP,普及组试题精解,在输入文件中有,n,个整数，每个数都在,1500,万之间，从这些数中选出,k,个整数进行相加，可得到不同的组合。,例如：有,4,个整数,8,、,11,、,12,、,13,，用其中的,3,个数进行相加，可得到如下所示的,4,种组合：,8+11+12=31,8+11+13=32,8+12+13=34,11+12+13=36,在以上的,4,个和值中，只有,8+11+12=31,的结果为素数。,现在要求你编写程序，计算给定,n,个整数，从中选中,k,个整数进行组合相加，其和值为素数的情况有多少种？,9.1.2 求素数组合,9.1 NOIP,普及组试题精解,在中国象棋中，卒过了界河以后不仅可以向前移动，也可以横向移动。现在假设有一个过河的卒位地图,9-3,所示的,A,点，要使该卒从,A,点移到,B,点（目标位置）可有多少种不同的路线？,9.1.3 计算卒的路线,9.1 NOIP,普及组试题精解,对于正式出版的图书，都必须有一个,ISBN,码。,ISBN,码一共有,10,位数字，前,9,位分别表示国家、出版者、书名号，最后一位是根据前,9,位数字计算得来的，作为校验码使用。一般,ISBN,的格式如下：,7-118-01984-4,以上,ISBN,码中，,7,表示中国，,118,表示国防工业出版社，,01984,代表书名号，最后一位,4,表示校验码。,校验码是其他,9,位数字的求余函数。计算方法是：用,10,2,这九个数分别顺序乘以,ISBN,的前九位数字，所得乘积之和被模数,11,除，其余数与,11,的差，即是校验位的数值。所以，校验位的数值可能是,1,11,中的任何一个整数，当校验位为,10,时，用大写字母“,X”,表示；当校验位为,11,时，用“,0”,表示。由此可见校验位只能是,0,、,1,、,2,、,3,、,4,、,5,、,6,、,7,、,8,、,9,、,X,，恒为一位数。,9.1.4 检查校验码,9.1 NOIP,普及组试题精解,六（一）班有几个调皮的同学，当这些同学坐在相邻位置（前后或左右相邻）时，在上课的时候总是会交头接耳，影响其他同学上课。这让班主任李老师非常头疼。,为了尽量减少这种现象，李老师想到一个办法，将这些上课喜欢说话的同学用过道分开。即某两个左右相邻的同学经常上课说话，则从这两个同学之间增加一条纵向过道，让他们的距离拉开，即可杜绝他们两个上课说话了。同样，若前后相邻同学喜欢上课说话，也在他们之间增加一条横向过道，将他们的距离拉开。,李老师决定按这种办法重新安排教室中的过道，以尽量减少上课时私下说话的同学的数量。如果教室中共有,M,行,N,列桌椅，需设置,K,条横向过道和,L,条纵向地道。请你编写程序，从输入文件中读入上课时喜欢私下说话的,D,对同学的坐标位置，然后根据这些已知条件，设计出在什么位置设置横向和纵向过道可使上课时私下说话的同学的数量最少。,9.1.5 排座位,9.1 NOIP,普及组试题精解,输入数据：,5 6 1 2 3,4 2 4 3,2 2 1 2,3 4 3 5,输出数据,1,2 4,9.1.5 排座位,9.2 NOIP提高组试题精解,一个天平秤配有若干砝码，这些砝码的重量分别为1g、2g、3g、5g、10g、20g等6种，所有砝码的总重量不超过1000g，各种砝码的数量在输入文件中给出，要求根据输入文件中给出的各种重量的砝码数量，计算出该天平能称出的重量的种类数。,9.2.1 码码称重,9.2 NOIP提高组试题精解,爸爸每月给阿明,300,元零花钱，由阿明自己管理使用。阿明每个月会自己做一个预算，计算本月需要用多少钱，并且总能严格地执行预算，即每月花的钱与预算相同。,为了让阿明从小养成储蓄的习惯，爸爸建议阿明可以将没用完的钱（整百的钱）存在他那里，到年底将存的钱再加上,20%,的奖励还给阿明。,为此，阿明制定了一个储蓄计划：在每个月的月初，爸爸将零花钱给他后，根据这个月的预算，到月末手中还会有多于,100,元或恰好,100,元的钱，就将余下的钱中的整百部分交给爸爸存起来，剩余的钱留在自己手中。,9.2.2 阿明的零花钱,9.2 NOIP提高组试题精解,马上要过春节了，妈妈到超市进行大采购，一共购买,n,种年货商品。年货采购齐以后，妈妈决定将所有年货商品都合并到一起，好搬回家里。,每一次合并时，可以把两种商品合并到一起，消耗的体力等于两种商品的重量之和。可以看出，所有的商品经过,n-1,次合并之后，就只剩下一大包了。在合并这些商品时总共消耗的体力等于每次合并时所耗体力之和。,因为还要花大力气把这些年货商品搬回家，所以在合并这些商品时，要尽可能地节省体力。现在要求你给妈妈设计一种方案，让妈妈在合并这些商品时耗费的体力最少，并输出这个最小的体力耗费值。,9.2.3 购买年货,9.2 NOIP提高组试题精解,合唱队的队员在演出时一般是按这种形式排列队伍：最高的队员排在中间，然后各队员按身高降序向两侧排列。设有,K,位合唱队员，从左到右依次编号为,1,、,2,、,、,K,，他们的身高分别为,T1,、,T2,、,、,TK,，则他们的身高满足,T,1,T,2,.T,i+1,T,K-1,T,K,（,1=i=K,）。,现在合唱队有,N,个队员随机地站成一排（并未按高矮次序排列），要想构成演出时的中间高两边矮的队形，则需要请其中的,(N-K),位队员出列，使得剩下的,K,位队员正好排成合唱队形。,请你根据数据输入文件中给出的各队员的身高数据，计算最少需要几位队员出列，才能使使剩下的队员正好组成合唱队形。,9.2.4 调整队形,9.2 NOIP提高组试题精解,9.2.4 调整队形,9.2 NOIP提高组试题精解,将一副牌随机分成了,N,堆，编号分别为,1,、,2,、,、,N,。每堆上有若干张，但纸牌总数一定是牌堆数,N,的倍数。为了使各堆牌的张数相同，可以在任一堆上取若干张纸牌，然后移动其附近的两堆牌中。具体的移牌规则为：,（,1,）编号为,1,的牌堆上的牌，只能移到编号为,2,的牌堆上（因为编号为,1,的牌堆左侧没有牌堆）；,（,2,）编号为,N,的牌堆上的牌，只能移到编号为,N-1,的牌堆上（因为其右侧没有牌堆）；,（,3,）其他牌堆上的牌（例如编号为,i,的牌堆），可以向左移（编号为,i-1,的牌堆）或向右移（编号为,i+1,的牌堆）。,现在要你设计一个程序，用最少的移动次数使每堆上纸牌的数量相同。,9.2.5 均分纸牌,性格决定命运,专注成就人生,