现在的位置: 首页 > 综合 > 正文

动态规划4道题 (python和c++代码)

2013年08月28日 ⁄ 综合 ⁄ 共 4664字 ⁄ 字号 小 中 大 ⁄ 评论关闭
#encoding:utf-8
#求fibo数列的非递归版本：动态规划，可用来练练手
p=[]

def fibo(n):
     i=0
     p.append(1)
     p.append(1)
     for i in range(2,n+1):
          if i!=n:
               p.append(p[i-1]+p[i-2])
          else:
               return p[i-1]+p[i-2]

print fibo(10)


// poj1163.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//POJ1163 The Triangle
//动态规划 比较简单
//#include <iostream.h>
#define MAX 101
int triangle[MAX][MAX]=
{
{7},
{3,8},
{8,1,0},
{2,7,4,4},
{4,5,2,6,5}
};

int maxtri[MAX][MAX]={0};
int n;
int longestPath(int hight);

int _tmain(int argc, _TCHAR* argv[])
{
     printf("%d",longestPath(4));
     return 0;
}

int longestPath(int hight)
{
     int i,j;
     int curmax;
     int totalmax=0;
     maxtri[0][0]=triangle[0][0];
     for(i=1;i<hight;i++)
     {
          maxtri[i][0]=maxtri[i-1][0]+triangle[i][0];
          maxtri[i][i]=maxtri[i-1][i-1]+triangle[i][i];
          for (j=1;j<i;j++)
          {
               if(maxtri[i-1][j-1]>maxtri[i-1][j])
                    maxtri[i][j]=maxtri[i-1][j-1]+triangle[i][j];
               else
                    maxtri[i][j]=maxtri[i-1][j]+triangle[i][j];
               if (maxtri[i][j]>totalmax)
                    totalmax=maxtri[i][j];
          }
     }
     return totalmax;
}

#poj 2593
#Max Sequence
#最大递增数列
def max_sequ(data):
     i=0
     cursum=0
     curmax=0
     res=0
     buf=[0 for i in range(0,len(data))]
     #rebuf=[0 for i in range(0,len(data))]

     for i in range(0,len(data)):
          cursum+=data[i]
          if cursum<0:
               cursum=0
          if cursum>curmax:
               curmax=cursum
          buf[i]=curmax

     cursum=0
     curmax=0
     for i in range(len(data)-1,0,-1):
          cursum+=data[i]
          curi=0
          if cursum<0:
               cursum=0
          if cursum>curmax:
               curmax=cursum
          if(curmax+buf[i-1]>res):
               res=curmax+buf[i-1]
               curi=i

     print buf#,rebuf

     print 'location of i',curi+1
     return res
     
indata=[-5,9,-5,11,20,4,-32,68,-34,45]
print max_sequ(indata)

// poj1141.cpp : Defines the entry point for the console application.
//Brackets Sequence 括号序列

#include "stdafx.h"
#include "windows.h"
#define INT_MAX 999999
char data [100]="[][()]][" ;
int dlen ;

int d [100][100]={0};

int excnt =0;//用来统计动态规划的调用次数
//当前这个实例中：不用记忆搜索运行了44065次 而用了动态规划则只用了6321次
//可见其效率的差别
int bracket (int i ,int j )
{
           int k;  
           int answer;
           excnt++;
           if ( i> j)
          {
                    return 0;
          }
           else if( i== j)
          {
                    return 1;
          }
           else
          {
                    answer= INT_MAX;
                    if (( data[ i]== '(' && data[ j]== ')')||
                             ( data[ i]== '[' && data[ j]== ']'))
                   {
                              if ( d[ i+1][ j-1]==0)
                             {
                                       answer= min( answer, bracket( i+1, j-1));
                             }
                              else
                                       answer= min( answer, d[ i+1][ j-1]);
                              d[ i][ j]= answer;
                             
                   }
                    if ( data[ i]== '('|| data[ i]== '['||
                              data[ i]== ']'|| data[ i]== ']')
                   {
                              if ( d[ i+1][ j]==0)
                             {
                                       answer= min( answer, bracket( i+1, j)+1);
                             }
                              else
                                       answer= min( answer, d[ i+1][ j]+1);
                              d[ i][ j]= answer;
                             
                   }
                    if ( data[ j]== ')'|| data[ j]== ']'||
                              data[ j]== '('|| data[ j]== '(')
                   {
                              if( d[ i][ j-1]==0)
                             {
                                       answer= min( answer, bracket( i, j-1)+1);
                             }
                              else
                                       answer= min( answer, d[ i][ j-1]+1);
                       d[ i][ j]= answer;
                   }

                    for ( k= i; k< j-1; k++)
                   {
                              answer= min( answer, bracket( i, k)+ bracket( k+1, j));
                   }
          }
           return answer;
}


int _tmain (int argc , _TCHAR * argv [])
{
           int res;
           int i, j;
           for ( i=0; i<100; i++)
          {
                    for ( j=0; j<100; j++)
                   {
                              if( i== j)
                                       d[ i][ j]=1;
                   }
          }
           res= bracket(0, strlen( data)-1);
           printf( "%d\nexcnt=%d" ,res ,excnt );
           return 0;
}
  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞