posts - 21,  comments - 9,  trackbacks - 0
  2014年7月18日
我的新博客大部分都发表到了kanhaide.blogspot.com,欢迎光临。
posted @ 2014-07-18 00:45 崔佳星 阅读(5111) | 评论 (0)编辑 收藏
  2012年4月15日
     摘要: 硬币找钱问题问题描述设有6种不同面值的硬币,各硬币的面值分别为5分,1角,2角,5角,1元,2元。现要用这些面值的硬币来购物和找钱。购物时规定了可以使用的各种面值的硬币个数。假定商店里各面值的硬币有足够多,顾客也可用多种方式支付。在1次购物中希望使用最少硬币个数。例如,1次购物需要付款0.55元,没有5角的硬币,只好用2*20+10+5共4枚硬币来付款。如果付出1元,找回4角5分,同样需要4枚硬币...  阅读全文
posted @ 2012-04-15 10:33 崔佳星 阅读(1134) | 评论 (6)编辑 收藏
  2011年4月24日
     摘要: 今天刷刷我们学校的OJ。看到了那道我们大家都熟悉的表达式求值题目。去网上搜了下,发现没有现成可用的好的算法。于是自己花了点时间写了个。没有做过多优化,先发出来再说。   1#include<stdio.h>  2#include<string.h>  3#include<stack> &nb...  阅读全文
posted @ 2011-04-24 21:00 崔佳星 阅读(170) | 评论 (0)编辑 收藏
  2011年2月16日
     摘要: n阶幻方问题:设n为奇数(n∈[3, 19])。试在n´n的表格内不重复地填上1, 2, …, n2数字,使得横向、纵向、两对角线上数之和都相等。   1#include<stdio.h>  2#include<malloc.h>  3//此程序适用于幻方问题 &nbs...  阅读全文
posted @ 2011-02-16 19:43 崔佳星 阅读(274) | 评论 (0)编辑 收藏
      终于到了开始学习算法的时刻了,心情好激动。去年暑假申请的这个博客又派上用场了,我会把我最近写的算法都发表在这里,希望大家喜欢,共同进步~
posted @ 2011-02-16 19:23 崔佳星 阅读(147) | 评论 (0)编辑 收藏
  2010年8月21日
     摘要: 1000        A+B Problem        送分题1001        Exponentiation      ...  阅读全文
posted @ 2010-08-21 20:07 崔佳星 阅读(459) | 评论 (0)编辑 收藏

贪心算法,使用STL的priority_queue来维护一个队列。保证鱼数最多(相同鱼则保存标号较小的)的一个序列。然后贪心就可以了。一下是代码
#include<iostream>
#include<queue>
using namespace std;
int n,h;
int f[30],t[30],d[30];
int best[30],way[30],maxinum,tot,tag=0;
struct node
{
 int num;
 int fish;
 void set(int id,int f)
 {
  num=id;
  fish=f;
 }
};
bool operator<(const node a,const node b)
{
 if(a.fish==b.fish)
  return a.num>b.num;
 else
  return a.fish<b.fish;
}
priority_queue<node> qu;
node now;
int main()
{
 while(scanf("%d",&n)&&n)
 {
  if(tag)
   printf("\n");
  cin>>h;
  h*=12;
  maxinum=-1;
  int i,j;
  for(i=0;i<n;i++)
  {
   cin>>f[i];
  }
  for(i=0;i<n;i++)
  {
   cin>>d[i];
  }
  for(i=0;i<n-1;i++)
  {
   cin>>t[i];
  }
  ///////////数据输入完毕,开始进入计算
  for(i=0;i<n;i++)
  {
   memset(way,0,sizeof(way));
   while(!qu.empty())
    qu.pop();
   if(i>0)
    h-=t[i-1];
   tot=0;   
   for(j=0;j<=i;j++)
   {
    now.set(j,f[j]);
    qu.push(now);    
   }
   for(j=0;j<h;j++)
   {
    now=qu.top();
    qu.pop();
    tot+=now.fish;
    now.fish-=d[now.num];
    if(now.fish<0)
     now.fish=0;
    way[now.num]+=5;
    qu.push(now);
   }
   if(tot>maxinum)
   {
    maxinum=tot;
    memcpy(best,way,sizeof(way));
   }

  }
  printf("%d",best[0]);
  for(i=1;i<n;i++)
   printf(", %d",best[i]);
  printf("\nNumber of fish expected: %d\n",maxinum);
  tag=1;
 }
 return 0;

}

posted @ 2010-08-21 15:09 崔佳星 阅读(1303) | 评论 (1)编辑 收藏
  2010年8月20日

回溯法:八皇后问题,一个经典问题

     在程序设计中还有一种方法叫做"回溯法".他不是按照某种公式或确定的法则,求问题的解,而是通过试探和纠正错误的策略,找到问题的街.这种方法一般是从一个原始状态出发,通过若干步试探,最后达到目标状态终止.
    回溯法在理论上来说,就是在一棵搜索树中从根结点出发,找到一条达到满足某条件的子结点的路径.在搜索过程中,对于每一个中间结点,他的位置以及向下搜索过程是相似的,因此完全可以用递归来处理.典型的例子就是著名的"八皇后问题".
    "八皇后问题"是在国际象棋棋盘上放置八个皇后,使她们不能相吃.国际象棋中的皇后可以吃掉与她处于同一行,同一列,同一对角线上的棋子.因此每一行只能摆放一个皇后.因共有八行,所以每行有且只有一个皇后.
    在本例中皇后的位置有一个一维数组来存放A(I)=J表示第I行皇后放在第J列.下面主要来看看怎么样判断皇后是否安全的问题.(1)首先,用一维数组来表示,已经解决了不在同一行的问题.(2)对于列可以引进一个标志数组C[J],若J列上已放了皇后,则C[J]=FALSE.(3)对于左上右下的对角线I-J为一常量,位于[-7,+7]之间,再此引入标志数组L[-7..7];对于左下右上的对角线,类似的有I+J等于常量,用数组R[2..16]来表示.当在第I行,第J列上放置了皇后,则只需设置:C[J]:=FALSE; L[I-J]:=FLASE; R[I+J]:=FALSE就可以解决皇后的安全问题了.

 

问题描述:在标准国际象棋的棋盘上(8*8格)准备放置8只皇后,我们知道,国际象棋中皇后的威力是最大的,她既可以横走竖走,还可以斜着走,遇到挡在她前进路线上的敌人,她就可以吃掉对手。要求在棋盘上安放8只皇后,使她们彼此互相都不能吃到对方,求皇后的放法。
/************************************************************************/
/*                                   */
/*    问题:在8×8的国际象棋棋盘上放置8个皇后,要求任意两个皇后       */
/*       不能在同一行、同一列或同一条对角线上。             */
/*                                   */
/*    本程序使用递归-回溯法求解8皇后问题。Visual C++ 6.0 调试通过。  */
/*    作者 晨星     2002年5月9日                   */
/*                                   */
/************************************************************************/
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define QUEENS 8
//!记录解的序号的全局变量。
int iCount = 0;
//!记录皇后在各列上的放置位置的全局数组。
int Site[QUEENS];
//!递归求解的函数。
void Queen(int n);
//!输出一个解。
void Output();
//!判断第n个皇后放上去之后,是否有冲突。
int IsValid(int n);
/*----------------------------Main:主函数。 ----------------------------*/
void main()
{
     //!从第0列开始递归试探。
     Queen(0);
     //!按任意键返回。
     getch();
}
/*-----------------Queen:递归放置第n个皇后,程序的核心!----------------*/
void Queen(int n)
{
     int i;
     //!参数n从0开始,等于8时便试出了一个解,将它输出并回溯。
     if(n == QUEENS)
     {
           Output();
           return;
     }
      
     //!n还没到8,在第n列的各个行上依次试探。
     for(i = 1 ; i <= QUEENS ; i++)
     {
           //!在该列的第i行上放置皇后。
           Site[n] = i;
           //!如果放置没有冲突,就开始下一列的试探。
           if(IsValid(n))
                 Queen(n + 1);
     }
}
/*------IsValid:判断第n个皇后放上去之后,是否合法,即是否无冲突。------*/
int IsValid(int n)
{
     int i;
     //!将第n个皇后的位置依次于前面n-1个皇后的位置比较。
     for(i = 0 ; i < n ; i++)
     {
           //!两个皇后在同一行上,返回0。
           if(Site[i] == Site[n])
                 return 0;
           //!两个皇后在同一对角线上,返回0。
           if(abs(Site[i] - Site[n]) == (n - i))
                 return 0;
     }
     //!没有冲突,返回1。
     return 1;
}
/*------------Output:输出一个解,即一种没有冲突的放置方案。------------*/
void Output()
{
     int i;
     //!输出序号。
     printf("No.%-5d" , ++iCount);
     //!依次输出各个列上的皇后的位置,即所在的行数。
     for(i = 0 ; i < QUEENS ; i++)
           printf("%d " , Site[i]);
     printf("n");
}


STL源代码
用了STL, 方法是一样的.
#include <iostream>
#include <string>
using namespace std;
void queen(const string t, const string s)
{
    if (s=="") cout<<t<<endl;
    else
        for (int i=0; i<s.length(); i++) {
            bool safe=true;
            for (int j=0;j<t.length();j++) {
                if (t.length()-j==abs(s[i]-t[j])) safe=false;
            }
            if (safe) queen(t+s[i], s.substr(0,i)+s.substr(i+1));
    }
}
int main()
{
            string s="01234567";
    queen("",s);
    system("PAUSE");
    exit(EXIT_SUCCESS);
}

递归解八皇后问题
/*递归法解八皇后问题*/
/*作者黄国瑜,《数据结构(C语言版)》清华大学出版社*/
char Chessboard[8][8]; /*声明8*8的空白棋盘*/
int N_Queens(int LocX, int LocY, int Queens) /*递归*/
{
int i,j;
int Result=0;
if(Queens == 8)/*递归结束条件*/
   return 1;
else if(QueenPlace(LocX,LocY))/*递归执行部分*/
  {
  Chessboard[LocX][LocY] = 'Q';
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
    {
    Result += N_Queens(i,j,Queens+1);
    if(Result>0)
      break;
    }
  if(Result>0)
    return 1;
  else
    {
    Chessboard[LocX][LocY] = 'X';
    }
  }
else
  return 0;
}
int QueenPlace(int LocX,int LocY) /*判断传入坐标本身及入八个方向上是否有皇后*/
{
int i,j;
if(Chessboard[LocX][LocY] != 'X')
  return 0;
for(j=LocY-1;j>=0;j--)
  if(Chessboard[LocX][j] != 'X')
    return 0;
for(j=LocY+1;j<8;j++)
  if(Chessboard[LocX][j] != 'X')
    return 0;
for(i=LocX-1;i>=0;i--)
  if(Chessboard[i][LocY] != 'X')
    return 0;
for(i=LocX+1;i<8;i++)
  if(Chessboard[i][LocY] != 'X')
    return 0;
i= LocX - 1;
j= LocY - 1;
while (i>=0&&j>=0)
  if(Chessboard[i--][j--] != 'X')
    return 0;
i= LocX + 1;
j= LocY - 1;
while (i<8&&j>=0)
  if(Chessboard[i++][j--] != 'X')
    return 0;
i= LocX - 1;
j= LocY + 1;
while (i>=0&&j<8)
  if(Chessboard[i--][j++] != 'X')
    return 0;
i= LocX + 1;
j= LocY + 1;
while (i<8&&j<8)
  if(Chessboard[i++][j--] != 'X')
    return 0;
return 1;
}
main() /*主程序*/
{
int i,j;
for(i=0;i<8;i++)
  for(j=0;j<8;j++)
    Chessboard[i][j] = 'X';
N_Queens(0,0,0);
printf("the graph of 8 Queens on the Chessboard.is:n");
for(i=0;i<8;i++)
  for(j=0;j<8;j++)
  {
  if(Chessboard[i][j] == 'Q')
    printf("(%d,%d)n",i,j);
  }
getch();
}
/*********************************************************
*****************八皇后问题*******************************
************根据严书给的类c算法求得************************
*********************************************************/
#include<stdio.h>
#define N 8
int col=1,row=1,slash=1,bslash=1;
int a[N][N];
int p,q,k,l;
int num=0;
void trial(int i)
{
int j;   /*注 意,这里的j 一定要设为内部变量*/
if(i==N)
{
num++;
for(k=0;k<N;k++)
{
for(l=0;l<N;l++)
{
  if(a[k][l]==1)
   printf("@");
  else printf("*");
}
printf("n");
}
printf("nn");
getchar();
}
else
{
for(j=0;j<N;j++)
{
for(k=0;k<i;k++)
  if(a[k][j]==1)
  {
   col=0;
   break;
  }     /*列*/
p=i-1;
q=j+1;
while((p>=0)&&(q<N))
{
  if(a[p][q]==1)
  {
   slash=0;
   break;
  }
  p--;
  q++;
}
p=i-1;
q=j-1; /*对角*/
while((p>=0)&&(q>=0))
{
  if(a[p][q]==1)
  {
   bslash=0;
   break;
  }
  p--;
  q--;
}      /*斜对角*/
if((col==1)&&(slash==1)&&(bslash==1)) /*条件判断*/
{
  a[i][j]=1;
  trial(i+1);
}
col=1;slash=1;bslash=1;
a[i][j]=0;
}
}
}
void main()
{
trial(0);
printf("%dn",num);
getchar();
}

posted @ 2010-08-20 18:34 崔佳星 阅读(698) | 评论 (0)编辑 收藏
这是一个全排列算法的C++模板, 与STL中泛型算法next_permutation的功能是一样的。

template < typename T >
bool _next_permutation( T *first, T *last );
#define N 8
int main(int argc, char* argv[])
{
        int i;
        int y = 1;//序号
        char a[N];
        for ( i=0; i<N; i++ )
        {
                a[i] = i + 1 + 64 + 32;
        }

        long t0 = time( NULL );
        do
        {
                cout << y << " ---> ";
                for ( i = 0; i<N; i++ ) cout << a[i];
                cout << endl;

                y++;
        }while( _next_permutation( &a[0], &a[N] ) );
        long t1 = time( NULL ) - t0;
        cout << t1 << endl;//当N为8时耗时130秒,与泛型算法next_permutation用时一样

        return 0;
}

template < typename T >
bool _next_permutation( T *first, T *last )
{
        int i;
        int j;
        int x = -1;
        int rang = last - first;
       
        for ( i=0; i<rang-1; i++ )
        {
                if ( *( first+i ) <= *( first+i+1 ) )
                {
                        x = i;
                }
        }

        if ( x != -1 )
        {
                for ( i=x; i<rang; i++ )
                {
                        if ( *( first+x ) <= *( first+i ) )
                        {
                                j = i;
                        }
                }

                _swap( *( first+x ), *( first+j ) );

                for ( i=x+1; i<rang; i++ )
                {
                        if ( i != rang + x - i )
                        {
                                int nSwap = rang + x - i;
                                _swap( *( first+i ), *( first+ ( rang+x-i ) ) );
                        }
                        if ( ( i + 1 ) * 2 > rang + x )
                        {
                                break;
                        }
                }
        }

        if ( -1 == x ) return false;
        else return true;
}

template < typename T >
void _swap( T &a, T &b )
{
        a = a + b;
        b = a - b;
        a = a - b;
}

posted @ 2010-08-20 10:51 崔佳星 阅读(1761) | 评论 (2)编辑 收藏
  2010年8月19日

大整数的加法。与以前高精度算法不同的是这次要一下子读入一个算式。然后简便的是,这次不用再交换顺序了,直接加。但是结果的判断稍微麻烦一点,要把开头的0都去掉才行。一下是我的代码。哎,刚开始把自己弄得挺混乱的,后来愤怒了,就把所有代码全删掉重新写了一遍。然后一次AC
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
char a[12],b[12],c[12];
char temp[25];
bool add(char *first,char *second)
{
 int len1=strlen(first);
 int len2=strlen(second);
 first[len1]='0';
 int i,j;
 for(i=0;i<len2;i++)
 {
  second[i]-='0';
 }
 for(j=0;j<=len1;j++)
 {
  first[j]-='0';
 }
 for(i=0;i<len2;i++)
 {
  first[i]+=second[i];
 }
 for(i=0;i<len1;i++)
 {
  if(first[i]>=10)
  {
   first[i+1]+=first[i]/10;
   first[i]%=10;
  }
 }
 for(i=0;i<=len1;i++)
  first[i]+='0';
 while(first[len1]=='0')
  len1--;
 int len3=strlen(c);
 len3--;
 while(c[len3]=='0')
  len3--;
 if(len1!=len3)
  return false;
 while(len3>=0)
 {
  if(c[len3]!=first[len3])
   return false;
  len3--;
 }
 return true;
}
int main()
{
 while(gets(temp))
 {
  int kk=0;
  while(temp[kk]!='+')
  {
   a[kk]=temp[kk];
   kk++;
  }
  a[kk]='\0';
  kk++;
  int kkk=0;
  while(temp[kk]!='=')
  {
   b[kkk]=temp[kk];
   kk++;kkk++;
  }
  b[kkk]='\0';
  kk++;
  kkk=0;
  while(temp[kk]!='\0')
  {
   c[kkk]=temp[kk];
   kk++;kkk++;
  }
  c[kkk]='\0';

  int len1=strlen(a);
  int len2=strlen(b);
  if(len1==1&&len2==1&&a[0]=='0'&&b[0]=='0')
  {
   cout<<"True"<<endl;
   break;
  }
  if(len1>len2)
   if(add(a,b))
    cout<<"True"<<endl;
   else
    cout<<"False"<<endl;
  else
   if(add(b,a))
    cout<<"True"<<endl;
   else
    cout<<"False"<<endl;
 }
 return 0;

}

posted @ 2010-08-19 16:26 崔佳星 阅读(957) | 评论 (0)编辑 收藏
仅列出标题  下一页
<2019年2月>
272829303112
3456789
10111213141516
17181920212223
242526272812
3456789

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜