求两个算法

Question

1.有8号牌和9号牌无限张，请问使用这两种牌组合不出来的最大的数是多少?
例如：17可以由一张8号牌和9号牌组合而成，但是19就无法由这两种牌组合出来了
2.2008条线最多能将平面分为多少块?

Answer 1

2.数学几个问题：
1条直线.将平面分为两个部分
2条直线.较之前增加1条直线.增加1个交点.增加了2个平面部分
3条直线.与之前两条直线均相交.增加2个交点.增加了3个平面部分
4条直线.与之前三条直线均相交.增加3个交点.增加了4个平面部分
......
n条直线.与之前n-1条直线均相交.增加n-1个交点.增加个n个平面部分
所以n条直线分平面的总数为2+(2+3+4+5+6+7+8+ ...n)=1+(1+2+3+4+5+6+7+8+ ...n)=1+〔n＊(n+1)/2〕=(n2+n+2)/2 
总之：N条线可以最多将平面分为： n(n+1)/2+1个或(n²+n+2)/2快。即2008（2008+1）/3=1344690

Answer 2

2008条线最多能将平面分为多少块，第一眼看到的时候就觉得跟那个什么菲数列的求法差不多，因为大家都是数列来的，只要找到了规律，什么问题都可以用递归来解决。当然那个什么菲数列的解答中，大家很容易想到的还是那个f(n)=f(n-1)+f(n-2);但是如果这样算的话效率及其的低下，下面我给出我写的代码。#include <cstdlib>
#include <iostream>
using namespace std;
int func(int end,int first,int second)
{
    static int k=0;
    if(end==0)return first;
    if(end==1)return second;
    k++;
    end-=1; //缩短数列
    first+=k;
    second+=k+1;
    return func(end,first,second);//每次递归都会缩短数列
};
int cutpices(int end)
{
    return func(end,1,2);
};int main(int argc, char *argv[])
{
    cout<<cutpices(2008)<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}输出结果是2017037有8号牌和9号牌无限张，请问使用这两种牌组合不出来的最大的数是多少例如：17可以由一张8号牌和9号牌组合而成，但是19就无法由这两种牌组合出来了感觉用笔都能算出来，但是现在是要用程序实现（既然能用笔算出来了，程序就跟着思路跑了，代码待给出）首先我们发现一个规律：n个9比n个8大n（感觉有点像是废话），那么我们就想什么时候n个9比n+1个8还大呢，这样你就会使用表达式9n>8（n+1）来算。其实这里面最大的一个规律是：从8n到9n这段区间的任何一个数都是可以用8和9来组合得来的，并且9n会随着n的增大而与8n相差更大，好，那么只要找到n个9比n+1个8大的临界点，后面的都不用算了，因为后面的n值都会导致n个9比n+1个8大。总的一句就是，这道题要求解的是一段段的区间什么时候开始相邻或有交集，仅此而已。

Answer 3

2L的意思是3条直线比2条直线增加3个平面部分
f(n) = f(n-1) + n

Answer 4

第一题：对于满足你条件的最大的数X， X+1必定能被表示
设X+1 = 8 * i + 9 * j
则X = 8 * i + 9 * j - 1
    = 8 * （i + 1） + 9 * （j - 1）
由题意 如果 (i+1) 或者 (j-1) 不小于零 那么 X也能表示
因为X不能被表示 所以 （i+1）或者（j-1）小于零
又因为X+1能被表示 所以 i或者j 不小于零
从而有 j = 0也即 对于满足条件的X 它必定能被表示为8 * i - 1现在 考虑找出i的最大值
8 * i - 1
= 8 * （i-1） + 7
= 8 * （i-1） - 7 * 8 + 7 * 9
= 8 * （i-8） + 7 * 9      //该值设为T
如果T能被表示 则必须有 i-8不小于零
也即有 i不小于8
所以 满足条件的X i最大值为7   代入式子就有  X=55

Answer 5

1.有8号牌和9号牌无限张，请问使用这两种牌组合不出来的最大的数是多少?
例如：17可以由一张8号牌和9号牌组合而成，但是19就无法由这两种牌组合出来了
...无穷大2.2008条线最多能将平面分为多少块?
...n = math.pow(2, 2008);

Answer 6

这贴还没结啊。。第一题已经说过了  
第二题 LS已经有人说的很清楚了呀。。先归纳出公式吧设当前平面上已有n条直线  分割出的平面部分为f(n)块  根据这个来求f(n+1)1、当画上第n+1条直线时，最多增加了n个交点
不妨设这n个交点为i1,i2,...,in
对于线段 i1i2, i2i3, i3i4, ... in-1in 它们中的每一段都相当于在其原有所属块中分割出一块
（语文不好。。自己画个图理解）
所以，这些线段一共增加了n-1块平面
两端i1 in 由于直线的无限延伸，各增加了1块平面（也是画图就能明白的。。）综上，当已有n条直线的情况下，添加第n+1条直线 最多 可以增加 n + 1 块平面
从而有 f(n+1) = f(n) + n + 1一般的 f(n) = f(n-1) + n
       f(n-1) = f(n-2) + n - 1
       f(n-2) = f(n-3) + n - 2
       ………………………………
       ………………………………
       f(1) = f(0) + 1
上面所有式子相加 可得到
f(n) = f(0) + 1 + 2 + 3 + …… + n
     = f(0) + (n + 1） * n / 2
由题意 f(0) = 1  所以 f(n) = (n + 1) * n / 2 + 1
令n = 2008  则 总数为2017037发现2L最后敲计算器敲错了   话说LZ已经自己做出来了   速度结贴啊= =||

Answer 7

我是来搞乱的！
按照楼主的意思是同时要这两种牌来组成，chenchenyangll朋友的推理果然是严密，在他的推理过程中我加入一个条件即可达到同时需要这两种牌来组成的情况！
对于满足你条件的最大的数X， X+1必定能被表示
设X+1 = 8 * i + 9 * j（i为8号牌的张数，j为9号牌的张数，由此得出i>0且j>0）
则X = 8 * i + 9 * j - 1
  = 8 * （i + 1） + 9 * （j - 1）
由题意 如果 (i+1) 或者 (j-1) 不小于零 那么 X也能表示
因为X不能被表示 所以 （i+1）或者（j-1）小于等于零
因为i>0,所以i+1一定大于零，因为（j-1）<=0,又因为，j>0,所以:j=1
也即 对于满足条件的X 它必定能被表示为8 * i - 1现在 考虑找出i的最大值
8 * i - 1
= 8 * （i-1） + 7
= 8 * （i-1） - 7 * 8 + 7 * 9
= 8 * （i-8） + 7 * 9 //该值设为T
如果T能被表示 则必须有 i-8大于零
所以i最大为8
 代入式子X=8 * i + 9 * j - 1
         =8*8+9*1-1
         =72
所以，最大的，不能为8号牌和9号牌同时表示的数为：72