C++博客-sijing

HDOJ 1267下沙的沙子有几粒？（DP）

宇骐 — Mon, 02 Aug 2010 02:24:00 GMT

如果用f [ i ] [ j ]代表有i个H和j个D的序列的种数，则：
f [ i ][ j ] = f [ i-1 ][ j ] + f [ i ][ j-1 ]；
考虑最后一个字母是H还是D的情况，最后一个字母是D的情况的序列种数是f [ i ][ j-1 ]，最后一个字母是H的情况的序列种数是f [ i-1 ][ j ]。

#include <iostream>
#include <cstdio>//包含此头文件是为了调用C风格的输出函数printf.
using namespace std;

int main()
{
    __int64 a[21][21]={0};//也可以用memset(a,0,sizeof(a))需要包含头文件
    //不过我刚刚测试了一下，不包含头文件或者也没有关系。不懂！
    //甚至不初始化，该题也能AC！！！
    int i,j;
    for(i=0;i<=20;i++)
    {
        a[i][0]=1;//只要‘D’的个数为0，‘H’的个数为任意数，都是一种序列
        a[0][i]=0;//只要‘H’的个数为0，‘D’的个数为任意数，这种序列都不满足
    }
    for(i=1;i<=20;i++)
        for(j=1;j<=20;j++)
        {
            if(i<j)          //遇到‘H’个数少于‘D’个数时，这种序列不满足。
                a[i][j]=0;
            else             //‘H’个数大于或者等于‘D’个数时，进入状态转移方程
                a[i][j]=a[i-1][j]+a[i][j-1];///DP核心
        }
    int m,n;
    while(cin>>m>>n)
    {
        printf("%I64d\n",a[m][n]);
    }
    return 0;
}

宇骐 2010-08-02 10:24 发表评论

递推的方法推导错排算法

宇骐 — Sat, 08 May 2010 09:36:00 GMT

                            递推的方法推导错排算法:　　
                                          当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,
                                          那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.　　
                     第一步：把第n个元素放在一个位置,比如位置k,一共有n-1种方法;　　
                     第二步：放编号为k的元素,这时有两种情况.
                                                   ①把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;
                                                   ②不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法。　
         综上得到

M(n) = ( n - 1 ) [ M ( n - 2 ) + M ( n - 1 ) ]

特殊地，M ( 1 ) = 0 , M ( 2 ) = 1

宇骐 2010-05-08 17:36 发表评论

经典算法题目——最长公共子序列问题

宇骐 — Sun, 25 Apr 2010 11:33:00 GMT

给定两个序列
X = { x1 , x2 , ... , xm }
Y = { y1 , y2 , ... , yn }
求X和Y的一个最长公共子序列

举例
X = { a , b , c , b , d , a , b }
Y = { b , d , c , a , b , a }
最长公共子序列为
LSC = { b , c , b , a }

分析：

最长公共子序列问题具有最优子结构性质

设
X = { x1 , ... , xm }
Y = { y1 , ... , yn }
及它们的最长子序列
Z = { z1 , ... , zk }

则

1、若 xm = yn ，则 zk = xm = yn，且Z[k-1] 是 X[m-1] 和 Y[n-1] 的最长公共子序列
2、若 xm != yn ，且 zk != xm , 则 Z 是 X[m-1] 和 Y 的最长公共子序列
3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 的最长公共子序列

由性质导出子问题的递归结构

当 i = 0 , j = 0 时 , c[i][j] = 0
当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1
当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }

////////////////////////////////////////
这种分析方法比较有用，值得保存，book
----《计算机机算法设计与分析》电子工业出版社
////////////////////////////////////////

// 书中只有关键部分的代码，现在已经补全
// 源程序

#include "iostream.h"
#include "iomanip.h"

#define max 100

void LCSLength( int m , int n , char *x , char *y , char *b )
{
int i , j , k;
int c[max][max];

        for( i = 1 ; i <= m ; i++ )
        {
              c[i][0] = 0;
        }
        for( i = 1 ; i <= n ; i++ )
        {
             c[0][i] = 0;
        }
       for( i = 1 ; i <= m ; i++ )
      {
             for( j = 1 ; j <= n ; j++ )
             {
                   if( x[i-1] == y[j-1] )
                   {
                             c[i][j] = c[i-1][j-1] + 1;
                             k = i * ( n + 1 ) + j;
                            b[k] = '\\';
                   }
                  else if( c[i-1][j] >= c[i][j-1] )
                 {
                            c[i][j] = c[i-1][j];
                            k = i * ( n + 1 ) + j;
                            b[k] = '|';
                 }
                 else
                {
                       c[i][j] = c[i][j-1];
                      k = i * ( n + 1 ) + j;
                         b[k] = '-';
                 }
           }
      }

}
void LCS( int i , int j , char *x , char *b , int width )
{
           if( i == 0 || j == 0 )
                  return;
          int k = i * ( width + 1 ) + j;
          if( b[k] == '\\' )
         {
                LCS( i - 1 , j - 1 , x , b , width );
                cout<         }
         else if( b[k] == '|' )
        {
                 LCS( i - 1 , j , x , b , width );
         }
       else
        {
                LCS( i , j - 1 , x , b , width );
         }
}

void main()
{
      char x[max] = { 'a' , 'b' , 'c' , 'b' , 'd' , 'a' , 'b' };
      char y[max] = { 'b' , 'd' , 'c' , 'a' , 'b' , 'a' };
      int m = 7;
      int n = 6;
      char b[max] = { 0 };

LCSLength( m , n , x , y , b );
LCS( m , n , x , b , n );

cout<}

////////////////////////////////////////

宇骐 2010-04-25 19:33 发表评论

数组作为函数参数

宇骐 — Mon, 19 Apr 2010 08:15:00 GMT

一维数组作为函数参数问题：
首部：
        fun (int   a [ ]) 。
调用：fun ( 数组名 ) 。
多维数组作为函数参数问题：
形参必须是一个数组指针变量。
格式如下：
首部：<1>、fun ( int (*px) [N] ) 。
            <2>、fun ( int   x [ ] [N] ) 。
            <3>、fun ( int x [M] [N] ) 。
调用时: fun(数组名) 。

宇骐 2010-04-19 16:15 发表评论

小数位输出控制

宇骐 — Sat, 17 Apr 2010 17:37:00 GMT

按有效位输出是 setprecision，按小数位数输出也是setprecision，但到底是谁取决于fixed。

cout << resetiosflags(ios::fixed) << setprecision(n) << float-point-number; 是按n位有效数输出

cout << setiosflags(ios::fixed) << setprecision(n) << float-point-number; 是按n位小数输出

测试代码：

#include

using namespace std;

int main( void )

{

const double value = 12.3456789;

cout << value << endl; // 默认以6精度，所以输出为 12.3457

cout << setprecision(4) << value << endl; // 改成4精度，所以输出为12.35

cout << setprecision(8) << value << endl; // 改成8精度，所以输出为12.345679

cout << fixed << setprecision(4) << value << endl; // 加了fixed意味着是固定点方式显示，所以这里的精度指的是小数位，输出为12.3457
cout << value << endl; // fixed和setprecision的作用还在，依然显示12.3457

cout.unsetf( ios::fixed ); // 去掉了fixed，所以精度恢复成整个数值的有效位数，显示为12.35

cout << value << endl;

cout.precision( 6 ); // 恢复成原来的样子，输出为12.3457