说明案例讲稿1090chain

1、1090 Chain00348313 蒋竞1090 Chain拜特兰并不总是一个非常民主的国家，也有一些阴暗的历史。一个美好的日子，拜特将军该国的统帅作了一个用以结束长期内战的决定，释放被关押的反对派。然而，他并未让反对派的领袖拜特萨直接自由，而是用一根“拜特链”将拜特萨锁在墙边.该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起，但想除去它们却非常困难。 “将军，你为什么要用链子将我锁在墙边而不让我自由！”拜特萨大叫道。拜特萨，你并未完全被链子锁住，我可以坦率的告诉你，你完全可以从栅栏上解下环。”拜特将军不忠地回答，同时他补充说，“但是，你必须在夜里工作，一个小时之内完成，不能弄

2、出任何声音，否则，我将按有关法律制罪。”为了帮助拜特萨！链子上的环按整数1,2,n进行了编号。 我们可以按照以下规则解开环：l1每次有且只有一个环时可以被连接到栅栏或从栅栏上拆开。 l2 第1号环总能进行连接或拆开 l3 如果1,.,k-1 (1=kn)环都被拆开，第k个环被连接时, 此时我们能连接或拆开 第k+1个环. l, 问题： 计算拆除拜特链上全部环的最少操作次数Sample Input 4 / / 环的总数 1=n=1000 1 0 1 0 /在第2行有n个用一个空格分隔的整数 o1,o2,.,on (每个都是0或1)，如果 oi=1, 那么第I个环和栅栏相连，如果 oi=0, 那么

3、第I环没有和栅栏相连。 Sample Output 61010 - 1110 - 0110 - 0100 1100 - 1000 - 0000 1 2 3 4 5 6 问题抽象： 给定了一个由0和1 组成的字符串S (1 = n= 1000）允许进行以下两种操作： 将S的第一个字符取反。 若S1 . i 1 = 00000，Si = 1，那么将Si + 1取反。（1 = i = n 1）任务: 求最少经过多少步可以将字符串变为00000问题探讨如果出现 a1 a2 a3a(n-1) 1怎样把它变为000 00 呢？问题探讨如果出现 a1 a2 a3a(n-1) 1怎样把它变为000 00 呢？

4、a1 a2 a3a(n-1) 1问题探讨如果出现 a1 a2 a3a(n-1) 1怎样把它变为000 00 呢？a1 a2 a3a(n-1) 10 0 0 1 1问题探讨如果出现 a1 a2 a3a(n-1) 1怎样把它变为000 00 呢？a1 a2 a3a(n-1) 10 0 0 1 10 0 0 1 0问题探讨如果出现 a1 a2 a3a(n-1) 1怎样把它变为000 00 呢？a1 a2 a3a(n-1) 10 0 0 1 10 0 0 1 00 0 0 0 0问题探讨如果出现 a1 a2 a3a(n-1) 1怎样把它变为000 00 呢？a1 a2 a3a(n-1) 10 0 0

5、1 10 0 0 1 00 0 0 0 0引出新问题，如何将000 001变为000 000如果出现 a1 a2 a3a(n-1) 0则只需考虑如何把a1 a2 a3a(n-1) 变为0000则问题降了一级 变为n-1 级的问题回答刚才提出的问题如何将000 001变为000 000000001回答刚才提出的问题如何将000 001变为000 000000001000011回答刚才提出的问题如何将000 001变为000 000000001000011000010回答刚才提出的问题如何将000 001变为000 000000001000011000010000000又引出一个问题如何将0000

6、0变为00001如何将000 001变为000 000如何将00000变为00001000001 000011 - 000010 000000如何将000 001变为000 000如何将00000变为00001000001 000011 - 000010 00000001to00n=00to01n-1+1+01to00n-1如何将000 001变为000 000如何将00000变为00001000001 000011 - 000010 00000001to00n=00to01n-1+1+01to00n-1000000 000010 000011 00000100To01n=00To01n-1+

7、1+01To00n-1如何将000 001变为000 000如何将00000变为00001000001 000011 - 000010 00000001to00n=00to01n-1+1+01to00n-1000000 000010 000011 00000100To01n=00To01n-1+1+01To00n-1所以00To01n=01To00n=2*00To01n-1+1如果出现 a1 a2 a3a(n-1) 1,即an=1a1 a2 a3a(n-1) 1- 000 011 - 000 010- 00000如果出现 a1 a2 a3a(n-1) 1,即an=1a1 a2 a3a(n-1)

8、 1- 000 011 - 000 010- 00000s 表示字符串 则snTo00=sn-1To01+1+01To00n-1如果出现 a1 a2 a3a(n-1) 1,即an=1a1 a2 a3a(n-1) 1- 000 011 - 000 010- 00000s 表示字符串 则snTo00=sn-1To01+1+01To00n-1a1 a2 a3a(n-1) 1- 000 001 sn To01=sn-1To00如果出现 a1 a2 a3a(n-1) 0,即an=0a1 a2 a3a(n-1) 0- 000 000snTo00=sn-1To00a1 a2 a3a(n-1) 0- 000

9、010- 000 011- 000001snTo01=sn-1To01+1+01To00n-1归纳起来00To01n=01To00n=2*00To01n-1+1初始条件为00To011=1If an=1snTo00=sn-1To01+1+01To00n-1snTo01=sn-1To00a1=1 则 s1To00=1 s1To01=0If an=0snTo00=sn-1To00snTo01=sn-1To01+1+01To00n-1a1=0 则 s1To00=0 s1To01=1根据以上公式就可逐项求解问题就结束了吗？问题就结束了吗？大家又没有发现什麽问题？问题就结束了吗？大家又没有发现什麽问题？

10、其实我之前有提示哦，呵呵问题抽象： 给定了一个又0和1 组成的字符串S (1 = n= 1000）当n为1000时，结果是一个很大的数，有300多位所以必须用高精度运算但实际上我们碰到的运算就两种00To01n=01To00n=2*00To01n-1+1snTo00=sn-1To01+1+01To00n-1但实际上我们碰到的运算就两种00To01n=01To00n=2*00To01n-1+1snTo00=sn-1To01+1+01To00n-1将01To00n=2*00To01n-1+1视为01To00n=00To01n-1+00To01n-1+1实质上是一样的,都为Plus(char *num1,char *num2,char * result)只用所一个高精度加法就可以还有两点00To01n=01To00n=2*00To01n-1+1snTo00=sn-1To01+1+01To00n-1若记录s1To00 到snTo00 00To011 00To01n 实际上不会有如此大的存储空间还有两点0