sijing

2010年8月2日

HDOJ 1267下沙的沙子有几粒? (DP)

如果用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))需要包含头文件<cstring>
    
//不过我刚刚测试了一下,不包含头文件<string.h>或者<memory.h>也没有关系。不懂!
    
//甚至不初始化,该题也能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;
}

posted @ 2010-08-02 10:24 宇骐 阅读(382) | 评论 (2)编辑 收藏

2010年5月8日

递推的方法推导错排算法

                            递推的方法推导错排算法:  
                                          当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

  
                                                               

posted @ 2010-05-08 17:36 宇骐 阅读(158) | 评论 (0)编辑 收藏

2010年4月25日

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

 

给定两个序列
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<<x[i]<<endl;
         }
         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<<endl<<endl;
}

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

posted @ 2010-04-25 19:33 宇骐 阅读(1638) | 评论 (1)编辑 收藏

2010年4月19日

数组作为函数参数

一维数组作为函数参数问题:
首部
        fun (int   a [ ])
调用fun ( 数组名 )
多维数组作为函数参数问题:
形参必须是一个数组指针变量。

格式如下:
首部:<1>、fun ( int   (*px) [N] )
            <2>、fun ( int   x [ ] [N] )
            <3>、fun ( int   x [M] [N] )
调用时:  fun(数组名)

posted @ 2010-04-19 16:15 宇骐 阅读(93) | 评论 (0)编辑 收藏

2010年4月18日

小数位输出控制

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

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

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

测试代码:

#include <iostream>

#include <iomanip>

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

    cout << value << endl;

}

posted @ 2010-04-18 01:37 宇骐 阅读(866) | 评论 (0)编辑 收藏

仅列出标题  
<2019年10月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜