信息学奥赛之窗--进制

作者:薛琛    发布时间:2018/4/28 16:12:00    浏览:392

一、进制相关知识
1.进制表示

17.jpg
   表示b进制下的n+1位数。  
2.进制之间的转换

  • b进制向十进制转换(按权值展开)
    18.jpg 
    十进制向b进制转换:

    • 整数部分除以基数并倒取余数。

    • 小数部分乘以基数,并顺取整数部分

二、题目
1.【天平I】
一个天平,有N个重量未知的砝码,砝码重量可由你自由确定。砝码可任意放在天平的左右两边,但要求称出从1到M之间所有的重量,现给出N的值,请问M最大值为多少。
【分析】如下图分析


19.jpg 

2.【天平II】
一个天平,砝码分别为1g、3g、9g、27g、…、6561g…,每个砝码只有一个,要称重的物品放在天平的左侧,而砝码允许放在天平的左右两侧。已知一个物品的质量N (N≤10^8 ),问如何称重?
【分析】
  因为砝码可以放右侧、不放或者放左侧三种状态,因此可以将N转换成三进制后,将三进制中的0、1、2三个状态转换成 0、1 、-1 ,具体的说,就是0和1不变,2变成-1后,其高一位加1。

3.【天平III】
一个天平,砝码分别为1g、3g、9g、27g、… 、6561g…,每个砝码只有一个,要称重的物品放在天平的左侧,而砝码只允许放在天平的右侧。将由这个系统可以称出来的重量按从小到大的顺序进行排列,得到下列序列:1,3,4,9,10,…。问其中的第K个重量是多少?(数据规模:K≤10^5)
【分析】
  只允许放右侧,那么对于一个砝码只有两种状态,要么放,要么不放,那么可以用二进制来处理。将K转化为二进制,从低到高对应位上是1,则对应从小到大的对应砝码就使用,是0则表示该砝码未用。

4.有一个黑匣子,黑匣子里有一个关于 x 的多项式 p(x) 。我们不知道它有多少项,但已知所有的系数都是正整数。每一次,你可以给黑匣子输入一个整数,黑匣子将返回把这个整数代入多项式后的值。你可以在几步之内还原出整个多项式?
【分析】
      首先,输入 1 ,于是便得到整个多项式的所有系数之和.不妨把这个系数和记作 S .下一步,输入 S + 1 ,于是黑匣子返回
     an * (S + 1)^n + an-1 * (S + 1)^n-1 + … + a1 * (S + 1)^1 + a0
把这个值转换成 S + 1 进制,依次计算出每一位上的数,它们就是多项式的各项系数了。
  为什么是S+1?
--确保进制的基数大于最大的系数,第二次带入就应为系数和+1。


Copyright@2009-2018 株洲市南方中学 All Rights Reserved

湘公网安备 43020302000273号

湘ICP备18002763号-1  湘教QS7-200505-000292   投稿入口 校内办公入口

株洲市南方中学 学校地址:株洲市芦淞区董家塅

招生热线

0731-28550326

28552555