正文

短小C语言程序2006-01-19 20:01:00

【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/love0you0forever/9745.html

分享到：

　               *
                * * *
              * * * * *
            * * * * * * *
              * * * * *
                * * *
                  *　　　　　　　就这个图形
 

　 
#include

void fun(int row,int start,int finish,int m) {
    int i=0;
    if (row<1) return;
    for (;i<=finish;i++)
        if (i<=finish&&i>=start) printf("*");
        else printf(" ");
    printf("\n");
    m=(start)?m:1;
    fun(row-1,(m)?start+1:start-1,(m)?finish-1:finish+1,m);
}
void main() {
    fun(7,7/2,7/2,0);
    getchar();
}

 

将大于整数m且紧靠m的k个素数存入数组xx传回
#include
void jsValue(int m,int k,int xx[])
{
    int i,j,s=0;        
    for(i=m+1;k>0;i++)    //可以帮我解释这个for语句吗？能力有限不是很懂
        { for(j=2;j            if(i%j==0) break;
      if(i==j)
     { xx[s++]=i; k--;}
    }
}
main()
{
    int m,n,zz[100];
cout<<"请输入两个整数：";

cin>>m>>n;

jsValue(m,n,zz);

for(m=0;mcout<cout<}

 

读入任一含加、减运算的表达式并计算值。其中数为整数，每一数前有一字 符，
表达式用“=”结束，如输入：+20-4-5+168=

#include
#include

int main()
{
     char a[500];/*算术表达式*/
     int tmp;/*中间变量*/
     int sign;/*数字符号， 是'+' or '-'*/
     int result;/*运算结果*/
     while(scanf("%s", a) != EOF)
     {
           sign = 1;/*缺省为正*/
           result = 0;
           tmp = 0;
           for(int i = 0; i           {
                 if(*(a + i) == '+')
                 {
                       result += sign * tmp;
                       sign = 1;
                       tmp = 0;
                 }
           
                else if(*(a + i) == '-')
                {
                        result += sign * tmp;
                        sign = -1;
                        tmp = 0;
                }
                else if(*(a + i) == '=')/*等号输出结果*/
                {
                        result += sign * tmp;
                        printf("%d\n", result);
                }
                else
                {
                       tmp = tmp * 10 + *(a + i) - '0';

                }
           }

     }

     return 0;
}

/*输入魔方阶数，输出魔方阵*/
#include
#define N 11
main()
{int mojie,a[N][N]={0},j,i=0,m=1;
  do         /*输入阶数*/
  {printf("please input mojie:");
   scanf("%d",&mojie);}
  while(mojie>N||mojie<1||mojie%2==0);
    j=(mojie-1)/2;a[i][j]=m;  /*建立方阵*/
    while(m     { m++;
      i-=1;
      j+=1;
      if((i<0)&&(j>mojie-1))
 {i=i+2;
 j=j-1;}
      else
 {if(i<0)
     i=mojie-1;
  if(j>mojie-1)
    j=0;
  }
      if(a[i][j]==0)
  a[i][j]=m;
      else
  {i=i+2;
   j=j-1;
   a[i][j]=m;}}

   for(i=0;i     {for(j=0;j       printf("%d  ",a[i][j]);
       printf("\n");}
      }


把上面的加减表达式扩充一下：

**********表达式求值********

#include <iostream>
#include <stdlib.h>
#include <cmath>
using namespace std;
int instack(char x)
{
  switch (x)
  { case '+':
    case '-': return 1;
    case '*':
    case '/': return 2;
    case '(': return 0;
    case '#': return -1;
    case '^': return 3;
  } 
}

int income(char x)
{
  switch (x)
  { case '+':
    case '-':
    case '=': return 1;
    case '*':
    case '/': return 2;
    case '(': return 4;
    case '^': return 4;
  } 
}

double compute(double x, double y, char op)
{
  switch(op)
  { case '+': return x+y;
    case '-': return x-y;
    case '*': return x*y;
    case '/': if(y==0)
                { cerr<<"Divide by 0!\n"; exit; }
              return x/y;
    case '^': return pow(x,y);
  }   
}

double number(char& ch)
{
  double value=0;
  while((ch>='0')&&(ch<='9'))
  { value=10*value+ch-'0';
    cin>>ch;
  }
  if(ch=='.')
  { int r=10;
    cin>>ch;
    while((ch>='0')&&(ch<='9'))
    { value+=double(ch-'0')/r;
      r=10*r;
      cin>>ch;
    }
  }
  return value;   
}

int main(int argc, char *argv[])
{
  double x,y;
  char ch,op;
  double s1[20]; int top1=-1;
  char s2[20];  int top2=-1;
  
  s2[0]='#';
  do
  { cin>>ch;
    if((ch>='0')&&(ch<='9'))
      s1[++top1]=number(ch);
    if(ch==')')
    { while(s2[top2]!='(')
      { y=s1[top1--];
        x=s1[top1--];
        op=s2[top2--];
        s1[++top1]=compute(x,y,op);
      }
      top2--; 
    }
    else
    { while( instack(s2[top2]) >= income(ch) )
      {
        y=s1[top1--];
        x=s1[top1--];
        op=s2[top2--];
        s1[++top1]=compute(x,y,op);
      }
      s2[++top2]=ch;
    }
  }while(ch!='=');
 
  cout<<s1[top1]<<endl;
   
  system("PAUSE");   
  return 0; 
}
 

再加点东西撒！


#include<iostream>
#include"Queue.h"
//五角星图遍历演示程序
//    A
// E    B
//  D  C
using namespace std;
class Graphic
{
private:
 int e[5][5];
 char v[5];
 Queue vertex[5];
public:
 Graphic();
 char GetValue(int);
 void DFS();
 void DFSHelper(int n,int *);
 void BFS();
 void BFSHelper(int,int *);
 void _DFS();
 void _DFSHelper(int,int *);//用队列处理得DFS
 int FirstNode(int );
 int NextNode(int,int);
 //start to link search
 void LBFS();
 void LBFSHelper(int,int *);
 int GetInt(char);
 void LDFS();
 void LDFSHelper(int,int *);
};
Graphic::Graphic()
{
 char carry='A';
 for(int i=0;i<5;i++)
 {
  v[  i]=carry;carry++;
 }
 e[0][0]=0;e[0][1]=0;e[0][2]=1;e[0][3]=1;e[0][4]=0;//初始化得是BD没联系得五角星
 e[1][0]=0;e[1][1]=0;e[1][2]=0;e[1][3]=0;e[1][4]=1;
 e[2][0]=1;e[2][1]=0;e[2][2]=0;e[2][3]=0;e[2][4]=1;
 e[3][0]=1;e[3][1]=1;e[3][2]=0;e[3][3]=0;e[3][4]=0;
 e[4][0]=0;e[4][1]=1;e[4][2]=1;e[4][3]=0;e[4][4]=0;
 vertex[0].In('A');vertex[0].In('C');vertex[0].In('D');
 vertex[1].In('B');                  vertex[1].In('E');
 vertex[2].In('C');vertex[2].In('A');vertex[2].In('E');
 vertex[3].In('D');vertex[3].In('A');
 vertex[4].In('E');vertex[4].In('B');vertex[4].In('C');
}
char Graphic::GetValue(int i)
{
 return v[  i];
}
int Graphic::FirstNode(int n)
{
 for(int j=0;j<5;++j)
  if(e[  n][  j]==1)
   return j;
  return -1;
}
int Graphic::NextNode(int n,int m)
{
 for(int j=m+1;j<5;++j)
  if(e[  n][  j]==1)
   return j;
  return -1;
}
void Graphic::DFSHelper(int n,int *Visit)
{
 if(!Visit[  n])
 {
  cout<<"  "<  Visit[  n]=1;
 }
 //int w=FirstNode(n);//有更简单得写法
 //while(w!=-1)
 //{
 // if(!Visit[  w])
 //  DFSHelper(w,Visit);
 // w=NextNode(n,w);
 //}
    for(int j=0;j<5;++j)//这是我研究得最简单也最好得算法，省下了很多麻烦
  if(!Visit[  j] && e[  n][  j]==1)
   DFSHelper(j,Visit);
}
void Graphic::DFS()
{
 int Visit[5]={0};
 DFSHelper(0,Visit);
}
void Graphic::BFSHelper(int n,int *Visit)
{
 Queue q;q.In(n);int temp;
 while(!q.IsEmpty())
 {
  q.Out(temp);
  if(!Visit[temp])
  {
   cout<<"  "<   Visit[temp]=1;
  }
  for(int j=0;j<5;++j)
     if(!Visit[  j] && e[temp][  j]==1)
      q.In(j);
 }
}
void Graphic::BFS()
{  int Visit[5]={0};
   BFSHelper(0,Visit);
}
void Graphic::_DFSHelper(int n,int *Visit)//Queue to deal with
{
 Queue q;q.In(n);int temp;
 while(!q.IsEmpty())
 {
  q.Out(temp);
  if(!Visit[temp])
  {
   cout<<"  "<   Visit[temp]=1;
  }
  for(int j=0;j<5;++j)
  {  if(!Visit[  j] && e[temp][  j]==1)
     _DFSHelper(j,Visit);
  }
 }
}
void Graphic::_DFS()
{  int Visit[5]={0};
   _DFSHelper(0,Visit);
}
//start to link search
void Graphic::LBFSHelper(int n,int *Visit)
{
 Queue q;char temp;int m;Queue vertex2[5];
     for(int i=0;i<5;++i)
  {
   vertex2[  i].Make(vertex[  i].ReturnFront());
  }
 while(!vertex2[  n].IsEmpty())
 {
  vertex2[  n].Out(temp);
  q.In(GetInt(temp));
 }
 while(!q.IsEmpty())
 {
  q.Out(m);
  if(!Visit[  m])
  {  cout<<"  "<     Visit[  m]=1;
  }
  while(!vertex2[  m].IsEmpty())
  {
   vertex2[  m].Out(temp);
   if(!Visit[GetInt(temp)])
    q.In(GetInt(temp));
  }
 }
}
void Graphic::LBFS()
{  int Visit[5]={0};
   LBFSHelper(0,Visit);
}
int Graphic::GetInt(char ch)
{
    switch(ch)
 {
 case 'A':return 0;
    case 'B':return 1;
    case 'C':return 2;
    case 'D':return 3;
    case 'E':return 4;
 }
}
void Graphic::LDFS()
{  int Visit[5]={0};
   LDFSHelper(0,Visit);
}
void Graphic::LDFSHelper(int n,int *Visit)
{
 Queue q;char temp;int m;Queue vertex1[5];
     for(int i=0;i<5;++i)
  {
   vertex1[  i].Make(vertex[  i].ReturnFront());
  }
  vertex1[  n].Out(temp);
  q.In(GetInt(temp));
 while(!q.IsEmpty())
 {
  q.Out(m);
  if(!Visit[  m])
  {  cout<<"  "<     Visit[  m]=1;
  }
  while(!vertex1[  m].IsEmpty())
  {
   vertex1[  m].Out(temp);
   if(!Visit[GetInt(temp)])
   LDFSHelper(GetInt(temp),Visit);
  }
 }
}
int main()
{
 Graphic First;
 cout<<"深度遍历:";First.DFS();cout< cout<<"广度遍历:";First.BFS();cout< cout<<"链表深度遍历:";First.LDFS();cout< cout<<"链表广度遍历:";First.LBFS();cout<}
 
//所包含得队列代码:

#include
using namespace std;
template
class QueueNode
{
public:
 T value;
 QueueNode *Next;
 QueueNode(T _value):value(_value),Next(0){}
};
template
class Queue
{
private:
 QueueNode *Front;
 QueueNode *Rear;
 QueueNode *GetNew(T);
public:
 Queue():Front(0),Rear(0){}
 void Make(QueueNode *q);
 QueueNode *ReturnFront();
 bool IsEmpty(){  return Front==0?1:0;  }
 void In(T);
 void Out(T &);
};
template
void Queue::Make(QueueNode *q)
{
 while(q!=0)
 {
  In(q->value);
  q=q->Next;
 }
}
template
QueueNode *Queue::ReturnFront()
{  return Front;
}
template
QueueNode *Queue::GetNew(T _value)
{  QueueNode *p=new QueueNode(_value);
   return p;
}
template
void Queue::In(T _value)
{   QueueNode *q=GetNew(_value);
 if(IsEmpty())
 {  Front=q;
    Rear=Front;
    return;
 }
 Rear->Next=q;
 Rear=Rear->Next;
}
template
void Queue::Out(T &temp)
{
 if(IsEmpty())
 {
  cout<<"队列为空!无法出队列!";
  return;
 }
 QueueNode *q=Front;
 Front=Front->Next;
 temp=q->value;
 delete q;
}

//************************************
//下一个：图得拓扑排序

//************************************

#include<iostream>
using namespace std;
class Graphic
{
private:
 char vertex[9];//顶点
 int e[9][9];//边
 int Top[9];//装在TOPSORT得数组
 int k;//相应得数组标志
 //Domin;
 int InDegree[9];
public:
 Graphic();
 //利用DFS得拓扑排序，其实也相当于无后继拓扑排序
 void TopSort(int );
 void TopSortHelper(int,int *);
 void PrintTopSort();
 //Domin
 int Get();
 void NoPreTopSort();
};
//无先趋拓扑排序
void Graphic::NoPreTopSort()
{
 int w=1;int counts=0;
 k=0;
 while(w!=-1)
 {
  w=Get();
  if(w!=-1)
  {
   Top[  k++]=w;
   counts++;//记录找除得顶点数
   for(int j=0;j<9;++j)
    if(e[  w][  j]==1)
     --InDegree[  j];//对相应顶点入度－1
  }
 }
 if(counts<9)
 {  cout<<"存在循环链路，错误!";
    return;
 }
 for(int h=0;h<=k-1;++h)
  cout<<"  "<<Top[  h];
}
int Graphic::Get()
{
 for(int j=0;j<9;++j)
  if(InDegree[  j]==0)
  {  InDegree[  j]=-1;
     return j;
  }
  return -1;
}
Graphic::Graphic()
{   vertex[0]='A';k=0;
 for(int i=1;i<9;++i)
  vertex[  i]=vertex[  i-1]+1;
 e[0][0]=0;e[0][1]=0;e[0][2]=1;e[0][3]=0;e[0][4]=0;e[0][5]=0;e[0][6]=0;e[0][7]=1;e[0][8]=0;
 e[1][0]=0;e[1][1]=0;e[1][2]=1;e[1][3]=0;e[1][4]=1;e[1][5]=0;e[1][6]=0;e[1][7]=0;e[1][8]=0;
 e[2][0]=0;e[2][1]=0;e[2][2]=0;e[2][3]=1;e[2][4]=0;e[2][5]=0;e[2][6]=0;e[2][7]=0;e[2][8]=0;
 e[3][0]=0;e[3][1]=0;e[3][2]=0;e[3][3]=0;e[3][4]=0;e[3][5]=1;e[3][6]=1;e[3][7]=0;e[3][8]=0;
 e[4][0]=0;e[4][1]=0;e[4][2]=0;e[4][3]=1;e[4][4]=0;e[4][5]=1;e[4][6]=0;e[4][7]=0;e[4][8]=0;
 e[5][0]=0;e[5][1]=0;e[5][2]=0;e[5][3]=0;e[5][4]=0;e[5][5]=0;e[5][6]=0;e[5][7]=0;e[5][8]=0;
 e[6][0]=0;e[6][1]=0;e[6][2]=0;e[6][3]=0;e[6][4]=0;e[6][5]=0;e[6][6]=0;e[6][7]=0;e[6][8]=0;
 e[7][0]=0;e[7][1]=0;e[7][2]=0;e[7][3]=0;e[7][4]=0;e[7][5]=0;e[7][6]=0;e[7][7]=0;e[7][8]=1;
 e[8][0]=0;e[8][1]=0;e[8][2]=0;e[8][3]=0;e[8][4]=0;e[8][5]=0;e[8][6]=1;e[8][7]=0;e[8][8]=0;
 int m;
    for(int j=0;j<9;++j)
 {   m=0;
  for(int i=0;i<9;++i)
   if(e[  i][  j]==1)
    m++;
  InDegree[  j]=m;
 }
}
void Graphic::TopSort(int n)
{
 int Visit[9]={0};
 TopSortHelper(n,Visit);
}
void Graphic::TopSortHelper(int i,int *Visit)
{
 if(!Visit[  i]) 
  Visit[  i]=1;
 for(int j=0;j<9;++j)
   if(!Visit[  j] && e[  i][  j]==1)
   TopSortHelper(j,Visit);
    Top[  k++]=i;
}
void Graphic::PrintTopSort()
{   int s;
    for(int j=0;j<9;++j)
 {   s=1;
  for(int i=0;i<9;++i)
   if(e[  i][  j]==1)
    s=0;
  if(s==1)
  {  TopSort(j);
  for(int j=k-1;j>=0;--j)
    cout<<"  "<<Top[  j];
  cout<<endl;
  k=0;
  }
 }
}
int main()
{
 Graphic First;
 cout<<"拓扑排序为:"<<endl;
 //First.PrintTopSort();
 First.NoPreTopSort();
}
 

//********************************

//********************************

//本程序演示动态规划思想

//关于01背包问题得解法

//********************************

//*******************************

#include<iostream>
using namespace std;
//背包问题解法
//重量{9,6,5,3,7,8,6,4}
//价钱{4,3,2,5,5,4,1,6}
//总容量40
//根据公式，方法有2，最优子结构自底向上的解法
//其次，递归配合备忘录方法求解，以达到较好效率
//c[  i][  j]= { max(c[  i+1][  j],c[  i+1][  j-w[  i]]+v[  i]能拿动的情况
//当不能拿动时c[  i][  j]=c[  i+1][  j];
int BeiBao(int,int,int);
void BeiBao2(int,int);
int w[9]={0,9,6,5,3,7,8,6,4};
int v[9]={0,4,3,2,5,5,4,1,6};
bool flag[9];//标志具体情况；
int s[9][41]={0};
int m[9][41]={0};
void FillFlag(int,int);
int main()
{
  //cout<<BeiBao(1,40,8)<<endl;
  //for(int i=1;i<9;++i)
 // cout<<"   "<<flag[  i];cout<<endl;
  //for(int i=1;i<9;++i)
// cout<<"   "<<w[  i];cout<<endl;
  //for(int i=1;i<9;++i)
 // cout<<"   "<<v[  i];cout<<endl;//背包1的递归主函数
 BeiBao2(8,40);
 FillFlag(8,40);
 cout<<m[1][40]<<endl;
 for(int i=1;i<9;++i)
  cout<<" "<<flag[  i];
}
int BeiBao(int i,int j,int n)
{
 if(i==n)
 {   if(j>=w[  i])
  { 
     if(s[  i][  j]==0)
     {   flag[  i]=1;
      s[  i][  j]=v[  i];
      return v[  i];
     }
     else
   {  
       return s[  i][  j];
   }
  }
  //flag[  i]=0;
  return 0;
 }
 if(j<w[  i])
 { 
  if(s[  i+1][  j]>0)
  return s[  i+1][  j];
    else
    {
     s[  i+1][  j]=BeiBao(i+1,j,n);
      flag[  i]=0;
     return s[  i+1][  j];
    }
 }
 if(j>=w[  i])
 {
        if(BeiBao(i+1,j,n)>BeiBao(i+1,j-w[  i],n)+v[  i])
        {  
    if(s[  i+1][  j]>0)
    return s[  i+1][  j];
   else
   {
    s[  i+1][  j]=BeiBao(i+1,j,n);
    flag[  i]=0;
    return s[  i+1][  j];
   }
  }
  if(BeiBao(i+1,j,n)<=BeiBao(i+1,j-w[  i],n)+v[  i])
  {  
   if(s[  i+1][j-w[  i]]>0)
   {
    return s[  i+1][  j-w[  i]]+v[  i];
   }
   else
   {
    s[  i+1][  j-w[  i]]=BeiBao(i+1,j-w[  i],n);
    flag[  i]=1;
    return s[  i+1][  j-w[  i]]+v[  i];
   }
  }
 }
}
void BeiBao2(int h,int k)
{
 for(int j=1;j<w[  h];++j)m[  h][  j]=0;
 for(int j=w[  h];j<=k;++j)m[  h][  j]=v[  h];
 for(int i=h-1;i>1;--i)
 {  for(int j=1;j<w[  i];++j)m[  i][  j]=m[  i+1][  j];
    for(int j=w[  i];j<=k;++j)m[  i][  j]=max(m[  i+1][  j],m[  i+1][  j-w[  i]]+v[  i]);
 }
 m[  1][  k]=m[  2][  k];
 if(k>w[  1])
  m[  1][  k]=max(m[  2][  k],m[  2][  k-w[  1]]+v[  1]);
}
void FillFlag(int n,int k)
{
 for(int i=1;i<n;++i)
 { if(m[  i][  k]==m[  i+1][  k])
   flag[  i]=0;
  else
  { flag[  i]=1;
      k-=w[  i];
  }
 }
 if(k>=w[  n])
  flag[  n]=1;
 else
  flag[  n]=0;
}
 

//******************************

//继续动态规划：最大公共子序列问题

//****************************

#include<iostream>
using namespace std;
void Find(int,int,char *,char *,int **,char **,bool **);
void List(int,int,char *,char **);
void List(int ,int ,char *,char *,bool **);
int main()
{
 char a[8]={'A','T','K','B','L','R','B','C'};
 char b[5]={'A','K','L','B','C'};
 int **s=new int *[9];char **p=new char *[9];bool **q=new bool *[9];
 for(int j=0;j<=8;++j)
 {
  s[  j]=new int[6];
  p[  j]=new char[6];
  q[  j]=new bool[6];
 }
 Find(8,5,a,b,s,p,q);
 List(8,5,a,p);
 //List(8,5,a,b,q);test the bool array,so is wrong!
}
void Find(int m,int n,char *a,char *b,int **s,char **p,bool **q)
{
 for(int i=0;i<=m;++i)
  s[  i][0]=0;
 for(int j=0;j<=n;++j)
  s[0][  j]=0;
     s[0][0]=0;
 for(int i=1;i<=m;++i)
  for(int j=1;j<=n;++j)
  {
   if(a[  i-1]==b[  j-1])
   {
    s[  i][  j]=s[  i-1][  j-1]+1;
    p[  i][  j]='*';
    q[  i][  j]=1;
   }
   else
   { if(s[  i-1][  j]>s[  i][  j-1])
        {
     s[  i][  j]=s[  i-1][  j];
     p[  i][  j]='s';
     q[  i][  j]=0;
     }
    else
    {
     s[  i][  j]=s[  i][  j-1];
     p[  i][  j]='z';
     q[  i][  j]=0;
    }
   }
  }
}
void List(int i,int j,char *a,char **p)
{
 if(i==0 || j==0)return;
 if(p[  i][  j]=='*')
 {
  List(i-1,j-1,a,p);
  cout<<"  "<<a[  i-1];
 }
 else if(p[  i][  j]=='s')
   List(i-1,j,a,p);
   else if(p[  i][  j]=='z')
      List(i,j-1,a,p);
}
void List(int m,int n,char *a,char *b,bool **q)
{
 for(int i=1;i<=m;++i)
  for(int j=1;j<=n;++j)
  {
   if(q[  i][  j]==1 && a[  i-1]==b[  j-1])
    cout<<"  "<<a[i-1];
  }
}

  

//******************************

//继续动态规划：最大递增公共子序列问题

//*********************************

#include<iostream>
using namespace std;
int main()
{   const int n=20;
 int x[  n]={11,15,12,56,5,12,13,8,33,9,65,15,16,19,58,54,84,23,51,25};
 int f[  n];
 for(int i=0;i<n;++i)
  f[  i]=1;
 for(int i=1;i<n;++i)
  for(int j=0;j<i;++j)
  {
            if(x[  j]<=x[  i] && f[  j]+1>f[  i])
     f[  i]=f[  j]+1;
  }
  cout<<"待求子序列:  ";
 for(int i=0;i<n;++i)
  cout<<" "<<x[  i];
 cout<<endl;
 cout<<"解决方案流程:";
    for(int i=0;i<n;++i)
    cout<<"  "<<f[  i];
    cout<<endl;
 int k,max,maxvalue;
 max=f[0];
    for(int i=1;i<n;++i)
  if(max<f[  i])
  { max=f[  i];
      k=i;
  }
  int d=k;
 for(int i=d+1;i<n;++i)
 {
  if(f[  i]==max)
  {
   if(x[  i]<x[  d])
    k=i;
  }
 }
  cout<<"最大递增子序列长度："<<max;
  cout<<"\n";
  int m=max-1,s=max,p;int flag[max+1];flag[max]=k;
 for(int j=m;j>=1;--j)
 {
  for(int i=0;i<k;++i)
  { if(f[  i]==j)
   {
    if(x[  i]<=x[  k])
    { flag[--s]=i;
        p=i;
    }
   }
  }
   k=p;
 }
 cout<<"最大递增的一个子序列:";
 for(int h=1;h<=m+1;++h)
  cout<<"  "<<x[flag[  h]];
}

 

//******************************

//继续动态规划：长矩阵相乘问题

//********************************

#include<iostream>
#include<iomanip>
using namespace std;
void Mul(int **x,int **y,int **z,int,int,int,int);
int BestDivived(int p[],int i,int j,int **m,int **s);
void DoDivived(int p[],int n,int **m,int **s);
void ShowDivived(int,int,int **s);
int main()
{
 int a[2][3]={4,2,3,1,5,2};
 int b[3][2]={2,1,4,5,3,2};
 int c[2][5]={6,5,8,9,7,4,5,6,5,5};
 int d[5][4]={6,5,4,1,2,5,4,5,4,6,9,8,9,5,6,3,2,1,4,5};
 int e[4][2]={5,4,6,5,5,6,5,3};
 int z[2][2]={0};
 int **s=new int *[5];
 int **m=new int *[5];
 for(int i=0;i<5;++i)
 {  s[  i]=new int[5];
    m[  i]=new int[5];
 }
 for(int i=0;i<5;++i)
       for(int j=0;j<5;++j)
  {   s[  i][  j]=0;
      m[  i][  j]=0;
  }
 int p[6]={2,3,2,5,4,2};
  //Mul(x,y,z,2,3,3,2);
  cout<<"=\n";
  DoDivived(p,5,m,s);
  for(int i=0;i<5;++i)
 {  
  for(int j=0;j<5;++j)
   cout<<setw(3)<<m[  i][  j];
   cout<<endl;
 }cout<<"\n";
 for(int i=0;i<5;++i)
 {  
  for(int j=0;j<5;++j)
   cout<<setw(3)<<s[  i][  j];
  cout<<endl;
 }
    cout<<endl;
    ShowDivived(0,4,s);
 
}
void Mul(int **x,int **y,int **z,int xr,int xl,int yr,int yl)
{
 int sum=0,m,k;
 if(xl!=yr)
  return;
 for(int j=0;j<yl;++j)
 { k=0;
  while(k<yl)
  {
  for(int i=0;i<xl;++i)
  { 
   m=x[  j][  i]*y[  i][  k];
   sum+=m;
  }
  z[  j][  k++]=sum;
  sum=0;
  }
 }
}
int BestDivived(int p[],int i,int j,int **m,int **s)
{  int k;
 if(m[  i][  j]>0) return m[  i][  j];
 if(i==j) return 0;
     int u=BestDivived(p,i,i,m,s)+BestDivived(p,i+1,j,m,s)+p[  i]*p[  i+1]*p[  j+1];
     s[  i][  j]=i;
     for(k=i+1;k<j;++k)
     {
      int q=BestDivived(p,i,k,m,s)+BestDivived(p,k+1,j,m,s)+p[  i]*p[  k+1]*p[  j+1];
      if(q<u)
    {   u=q;
           s[  i][  j]=k;
    }
     }
     m[  i][  j]=u;
     return u;
}
void DoDivived(int p[],int n,int **m,int **s)
{
 for(int i=0;i<n;++i)
  for(int j=0;j<n;++j)
   m[  i][  j]=0;
  BestDivived(p,0,n-1,m,s);
}
void ShowDivived(int i,int j,int **s)
{   static int k=0;
 if(i==j)return;
 ShowDivived(i,s[  i][  j],s);
 ShowDivived(s[  i][  j]+1,j,s);
 cout<<"("<<i<<"-"<<s[  i][  j];
 cout<<") * ("<<(s[  i][  j]+1)<<"-"<<j<<")"<<"level "<<k
 <<endl;++k;
}

 

//**********************************

//找零钱问题－－－－贪心算法小应用

//************************************

#include<iostream>
using namespace std;
//本程序为简单找零钱问题
//本问题针对零钱特殊情况，也就是能找开得情况讨论
//例子:零钱{25,10,5,1};
//总钱:63记录找开总钱得方案
const int n=4;
int a[  n+1]={0,25,10,5,2};
int c[  n+1]={0};
const int sum=63;
int Find(int,int *,int *,int );//贪心算法找最价值零钱;
void Print(int *,int);
//使用动态规划求解根据关系:c(i)=c(i-a[j])+1;
//于是可以采用两种方法对其求解；
//即:非递归方法 对总零钱数得数组都依次找最小解 但是这种情况针对能找到解得情况做
//递归方法
//非递归得动态规划
int s[sum]={0};
void FindCounts(int);
//递归方法
int DFindCounts(int,int);
int main()
{  
 cout<<"Sum is:"<<sum;
 cout<<"\n"<<"Find "<<DFindCounts(sum,1)<<endl;
 cout<<"选择对应零钱数量:";Print(c,n);
}
int Find(int n,int *a,int *c,int sum)
{   int k=0,i=1;
 while(sum>0)
 {  if(i>n) return 0;
  if(sum>=a[  i])
  {
   sum-=a[  i];
   k++;
   c[  i]++;
  }
  else
   i++;
 }
 return k;
}
void Print(int *p,int n)
{
 for(int i=1;i<=n;++i)
  cout<<"  "<<p[  i];
}
void FindCounts(int m)
{   s[0]=0;
 for(int i=1;i<=m;++i)
 {
  int min=i;
  for(int j=1;j<=n;++j)
    if(i>=a[  j] && s[  i-a[  j]]<min)
     min=s[  i-a[  j]];
    s[  i]=min+1;
 }
 cout<<s[m];
}
int DFindCounts(int m,int i)
{      
 if(m==0 || i>n)
  return 0;
 if(m<0)
  return -1;
 if(m>=a[  i])
 {   c[  i]++;
  return DFindCounts(m-a[  i],i)+1;
 }
 else
 return DFindCounts(m,i+1);
}

 

 

阅读(5216) | 评论(0)


版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！

评论

暂无评论
您需要登录后才能评论，请 登录 或者 注册