一、当n%6 != 2 且 n%6 !=
3时,有一个解为:

参考阅读

求所有可能出栈序列
判断出栈序列是否合法
卡特兰数_百度百科
从《编程之美》买票找零问题说起
Unique Binary Search
Trees

View Code

我们知道:1+2=3;
             4+5=9;
             2+3+4=9;
等式左边都是两个以上连续的自然数相加,那么是不是所有的整数都可以写成这种形式呢?

1、 括号化问题

 

问题2还可以用另一种角度来看,假设1代表入栈,0代表出栈,在2n位二进制数中填入n个1的方案数为c(2n,n),不填1的其余n位自动填0。从中减去不符合要求(由左而右扫描,0的累计数大于1的累计数)的方案数即为所求。
不符合要求的数的特征是由左而右扫描时,必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数,此后的2(n-m)-1位上有n-m个
1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换,使之成为n-m个0和n-m-1个1,结果得1个由n+1个0和n-1个1组成的2n位数,即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。
反过来,任何一个由n+1个0和n-1个1组成的2n位二进制数,由于0的个数多2个,2n为偶数,故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换,使之成为由n个0和n个1组成的2n位数,即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。
因而不合要求的2n位数与n+1个0,n-1个1组成的排列一一对应。
显然,不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=c(2n,n)-c(2n,n+1)=c(2n,n)/(n+1)=h(n)。

对每组测试数据,输出一行,包含一个“0
或一个“1”,即C(nk)除以2的余数。

问题1.
写一个程序,对于一个64位正整数,输出它所有可能的连续自然数(两个以上)之和的算式;

       

(当n为偶数,k=n/2;当n为奇数,k=(n-1)/2)

C(n) = C(0)C(n-1) + C(1)C(n-2) + … + C(n-1)C(0)
或者C(n) = (2n)! / (n!
(n+1)!)
C(0) = C(1) = 1
满足这样条件的序列就是卡特兰数。

威尼斯城真人赌钱网站 1威尼斯城真人赌钱网站 2

 PS: 64位整数为一种数据类型,即是pascal的int64以及c++的long long。能够表达-9223372036854775808到9223372036854775807之间的任意整数。

问题1:

num=i + i+1 + i+2 + ….+ i+k-1  一共有k个数。
= (i + i+k-1)*k/2
=(2*i+k-1)*k/2
=k*(i+ (k-1)/2)
=k*i + k*(k-1)/2
判断条件: num%(k*(k-1)/2)==0 或者 2*num>k*(k-1) 得:
k<sqrt(2*num) 
i=num/k;可得出i。

 

 

#include<iostream>
using namespace std;
void AddNum(__int64 num)
{
    __int64 k;
    __int64 i,t;
    __int64 j;
    int flag=-1;
    for (k=2;num>j;k++)//判断条件也可用sqrt(2*num),但是sqrt对64位的不好用。
    {
        if (k%2==0)
        {
            j=(k/2)*(k-1);//这样判断是为了节省计算的时间,因为k*(k-1)/2比(k/2)*(k-1)更费时间
        } 
        else
        {
            j=((k-1)/2)*k;
        }
        if (((num-j)%k)==0)
        {
            flag=1;
            i=(num-j)/k;
        }
        if (flag==1)
        {
            printf("%I64d = ",num);
            for (t=0;t<k;t++)
            {
                printf("%I64d",i+t);
                if ((t+1)<k)
                {
                    printf(" + ");
                }             
            }
            flag=0;
            cout<<endl;
        }
        if ((k+1)%2==0)
        {
            j=((k+1)/2)*k;
        } 
        else
        {
            j=(k/2)*(k+1);
        }
    }
    if (flag==-1)
    {
        printf("%I64d不可以表示成连续的自然数\n",num);
    } 
}    
void main()
{
    __int64 num;
    cout<<"请输入一个64位正整数:"<<endl;
    //cin>>num;  编译出错,cin适合32位的
    scanf("%I64d",&num);
    AddNum(num);
}

 

第二题:

解题思路:

因为num=(2*i+k-1)*k/2
接下来分析(2*i + k-1)*k*(1/2)的特征。

2*i为偶数。若k为奇数,k-1为偶数。则(2*i + k-1)*(1/2)
是一个整数。设为X。则num=k * X =奇数 *  X .

2*i为偶数。若k为偶数,k-1为奇数。则(2*i + k-1)为奇数。则 k*(1/2) 
是一个整数。设为X。则num=(2*i + k-1) * X =奇数 *  X .

由此可见,num的因式分解中必须含有一个奇数才可以表达成连续自然数相加的形式。

 

反证法:

如果num的因式分解中不含有奇数。设num= a * b .并且a 、b为偶数。

设a=(2*i +k-1) ,b=k/2. 
因为b为偶数,所以k为偶数。得出k-1为奇数。即(2*i
+k-1)为奇数。这与a是偶数矛盾。

设a=(2*i +k-1) /2,b=k.  因为a为偶数,所以(2*i
+k-1)为偶数。得出k-1为偶数。即k为奇数。这与b是偶数矛盾。

从程序输出结果上来看:

威尼斯城真人赌钱网站 3

 

由此推理得:这些数都是2的n次方。只要是2的n次方就不能转化成各个自然数连续相加的情形。
第三题

解题思路:

 

8位数中子序列最大的数是:(22个子序列)253 = 1 + 2 + 3 + 4 + 5 + 6 + 7 +
8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17+ 18 + 19 + 20 + 21 + 22

16位数中子序列最大的数是:(361个子序列)65341 = 1 + 2 + 3 + 。。。。+
358 + 359 + 360 + 361 

 。。。。。

设64位数中最大的子序列数位X。有k个子序列。

则X=1+2+3+。。。。+K=K*(1+K)/2

8位数:k*(k+1)/2 <0xFF 得到方程: k^2 + k -512 < 0 ,解方程得 k
<22.13.   取k=22.   从1+2+。。。+22就可以得到想要得到的数。

对于64位的数。同样利用上面的方程:k*(k+1)/2 <0xFFFFFFFFFFFFFFFF
得到方程: k^2 + k – (2*0xFFFFFFFFFFFFFFFF) < 0.

解方程得到: k <=6074000999   则num= 18446744070963499500

2、另一个递归式
      h(n)=((4*n-2)/(n+1))*h(n-1)
      它的解是:h(n)=C(2n,n)/(n+1)(n=1,2,3,…)

2,4,6,8,…,n-1,   1,3,5,7,…,n
(n为奇数)

  1. 1到n的整数能构建多少不同的BST(binary search tree)?
    任一个整数做根节点时,其左右BST子树的个数乘积就是这个整数做根节点的BST的个数,而1到n任一个整数做根节点的子树的个数相加,就是该问题的答案。例如:设该问题的解为h(n),
    1做根节点,则左子树不可能有节点,而2~n共n-1个节点构成了右子树,所以BST个数是h(0)h(n-1),
    k做根节点,则左子树只能有k-1个节点,而右子树只能有n-k个节点,此时BST个数是h(k-1)
    h(n-k),
    综上, h(n) = h(0)h(n-1) + h(1)h(n-2) + … + h(k-1)h(n-k) +
    … + h(n-1)
    h(0)。可以看出该问题的答案实际上就是求解卡特兰数
  2. 设有无穷大的栈,已知入栈序列为1,2,…,n,求所有可能的出栈序列的个数
    假设最后一个出栈的元素是k, 1 <= k <= n,
    则显然在k入栈之前,1到k-1已经全部出栈了;而在k入栈后,k+1到n开始入栈,并在k出栈前全部出栈完毕。设该问题的解是h(n),
    则显然当最后一个出栈的元素是k时,左右可能的出栈序列是h(k-1)h(n-k),
    而h(n) = h(0)
    h(n-1) + h(1)h(n-2) + … + h(k-1)h(n-k) + … +
    h(n-1)*h(0)。可以看出该问题的答案实际上也是求解卡特兰数。
  3. 有n对(),求所有可能的括号序列个数,比如n = 2时(()), ()()
    我们可以把'(‘看成入栈,’)’看成出栈,所以问题3实际上就等同于问题2
  4. 有2n个人买票,票价是5元,n个人有5元,n个人有10元,剧场没有零钱,有多少种可能排队,可以让所有人都买到票。
    我们可以吧5元看成入栈,10元看成出栈,所以问题4实际上就等同于问题2

  对于C(n,k),若n&k == k 则c(n,k)为奇数,否则为偶数。

二、
卡特兰数的应用

(上面序列第i个数为ai,表示在第i行ai列放一个皇后;…
省略的序列中,相邻两数以2递增。下同)二、当n%6 == 2 或 n%6 == 3时,

public class Solution {
    static void parenthese(String currentSeq, int leftLNum, int leftRNum) {
        if (leftRNum == 0) {
            System.out.println(currentSeq);
            return;
        }
        if (leftLNum == 0) {
            for (int i = 0; i < leftRNum; i++) {
                currentSeq += ")";
            }
            System.out.println(currentSeq);
            return;
        }
        if (leftLNum == leftRNum) {
            parenthese(currentSeq + "(", leftLNum - 1, leftRNum);
        } else {
            parenthese(currentSeq + "(", leftLNum - 1, leftRNum);
            parenthese(currentSeq + ")", leftLNum, leftRNum - 1);
        }
    }
    public static void parenthese(int n) {
        parenthese("", n, n);
    }
    static void printStack(final String seq) {
        int oneCount = 0;
        int zeroCount = 0;
        for (int i = 0; i < seq.length(); i++) {
            if (seq.charAt(i) == '1') {
                oneCount++;
            } else {
                if (seq.charAt(i - 1) == '1') {
                    System.out.print(oneCount);
                    zeroCount = 0;
                } else {
                    System.out.print(oneCount - zeroCount);
                }
                zeroCount++;
            }
        }
        System.out.print("\n");
    }
    static void stack(String currentSeq, int leftPushNum, int leftPopNum) {
        if (leftPopNum == 0) {
            printStack(currentSeq);
            return;
        }
        if (leftPushNum == 0) {
            for (int i = 0; i < leftPopNum; i++) {
                currentSeq += "0";
            }
            printStack(currentSeq);
            return;
        }
        if (leftPushNum == leftPopNum) {
            stack(currentSeq + "1", leftPushNum - 1, leftPopNum);
        } else {
            stack(currentSeq + "1", leftPushNum - 1, leftPopNum);
            stack(currentSeq + "0", leftPushNum, leftPopNum - 1);
        }
    }
    public static void stack(int n) {
        stack("", n, n);
    }
    public static void main(String[] argc) {
        parenthese(4);
        stack(4);
    }
}

Description

题目:

自己的理解:
一共有a0,a1,a2,…,an共n个元素,由它们来构造二叉树。h(n)表示这n个元素一共可以构成h(n)个不同的二叉树。如果选取a0作为根节
点,那么其左子树包含0个元素,左子树的数目是h(0);其右子树包含n-1个元素,右子树的数目是h(n-1);以a0为根节点的二叉树的数目是
h(0)*h(n-1)。如果选取a1作为根节点,那么其左子树包含1个元素a0,左子树的数目是h(1);其右子树包含h(n-2)个元素,右子树的数
目是h(n-2);以a1为根节点的二叉树的数目是h(1)*h(n-2)。如果选取ai作为根节点,其左子树包含i个元素,左子树的数目是h(i);右
子树包含n-i-1个元素,右子树数目为h(n-i-1);以ai为根节的二叉树的数目是h(i)*h(n-1-i)。
总的二叉树的数目为h(n)=h(0)*h(n-1)+h(1)*h(n-2)+…+h(i)*h(n-1-i)+…+h(n-1)*h(0)
如果一共有0个节点,那么二叉树的数目为h(0)=1;如果一共有1个节点,那么二叉树的数目为h(1)=1

相关文章