定理的证明:(充分性)用数归法:当 i=1 的时候,a(i) =1

简介: 定理的证明:(充分性)用数归法:当 i=1 的时候, a(i) =1 显然成立;假设 i=k 的时候定理充分性成立, 即用满足(1) 式的前 k 个砝码可以称量

定理: 由 m 个数构成的由小到大排列的数列{a(1) , a(2) , . . . a(m) } , 设 A(k) =∑a(i) , 其中 i 从 1 到 k, 则a(1) = 1 且 a(j+1) <= 2A(j) +1, j 取 1, 2, . . , m-1 (1 式)是该数列作为砝码序列可称量{0, 1, . . , Am} 范围内的任意整数重量的充要条件。

特别的, 上式取等号时,该序列是唯一可能的砝码序列, 并且有 a(j) = 3^(j-1) , 对于 j=1, 2, . . , m推论: 重量为 n 的物体要分成 m 份重量为整数的物体的序列{a(1) , a(2) , . . a(m) } ,设 M=∑3^(i-1) , 其中 i从 1 到 m, 则有三种情况:1) Mn, 可能有多组解, 解为满足(1 式) 并且∑a(i) =n, 其中 i 从 1 到 m, 的所有整数序列。

定理的证明:(充分性)用数归法:当 i=1 的时候, a(i) =1 显然成立;假设 i=k 的时候定理充分性成立, 即用满足(1) 式的前 k 个砝码可以称量的重量W(k) 为满足 0<=W(k) <=A(k)的所有整数, 则 i=k+1 时, 应可以称量 W(k+1) , 应为 0<=W(k+1) <=A(k+1) 范围内的所有整数。

分段讨论如下:(a) 对于 0<=W(k+1) <=A(k) , 显然可以由前 k 个砝码称量;(b) 对于 A(k)

与大砝码 a(k+1)一起使用可以得到 a(k+1) +W(k) ' , 一定可以称量某段连续范围的所有整数, 因为 a(k+1) <=2A(k) +1,所以 a(k+1) -A(k) <=A(k) +1, 因此 a(k+1) +W(k) ' 产生的下限为 a(k+1) -A(k) , 上限为 a(k+1) , 所以可以称量 A(k)

(必要性)i=1 时, 显然必须有总量为 1 的砝码;i>1 时, 反证之, 如果存在某个 K, 使得(1) 不成立, 即 2A(k) +1A(k) +1 而不能用 a(k+1) 配合着称重。

当 n=∑3^(i-1) , i 从 1 到 m 的时候, 有唯一解 a(i) =3^(i-1) , 可以改写成a(i) =2(∑aj) +1, 其中 j 从 1到 i-1, 一个循环就直接输出了; 当 n>∑3^(i-1) 的时候无解; 当 n<∑3^(i-1) 的时候只要根据式(1) 并保证∑a(i) =n 搜索就可以了。


以上是文章"

定理的证明:(充分性)用数归法:当 i=1 的时候,a(i) =1

"的内容,欢迎阅读天天向上教育网的其它文章