2012年4月15日
摘要: 硬幣找錢問題問題描述設(shè)有6種不同面值的硬幣，各硬幣的面值分別為5分，1角，2角，5角，1元，2元。現(xiàn)要用這些面值的硬幣來購物和找錢。購物時(shí)規(guī)定了可以使用的各種面值的硬幣個(gè)數(shù)。假定商店里各面值的硬幣有足夠多，顧客也可用多種方式支付。在1次購物中希望使用最少硬幣個(gè)數(shù)。例如，1次購物需要付款0.55元，沒有5角的硬幣，只好用2*20+10+5共4枚硬幣來付款。如果付出1元，找回4角5分，同樣需要4枚硬幣...
閱讀全文
2011年4月24日
摘要: 今天刷刷我們學(xué)校的OJ。看到了那道我們大家都熟悉的表達(dá)式求值題目。去網(wǎng)上搜了下，發(fā)現(xiàn)沒有現(xiàn)成可用的好的算法。于是自己花了點(diǎn)時(shí)間寫了個(gè)。沒有做過多優(yōu)化，先發(fā)出來再說。
1#include<stdio.h> 2#include<string.h> 3#include<stack> &nb...
閱讀全文
2011年2月16日
摘要: n階幻方問題：設(shè)n為奇數(shù)(n∈[3, 19])。試在n´n的表格內(nèi)不重復(fù)地填上1, 2, …, n2數(shù)字，使得橫向、縱向、兩對(duì)角線上數(shù)之和都相等。
1#include<stdio.h> 2#include<malloc.h> 3//此程序適用于幻方問題 &nbs...
閱讀全文
終于到了開始學(xué)習(xí)算法的時(shí)刻了，心情好激動(dòng)。去年暑假申請(qǐng)的這個(gè)博客又派上用場了，我會(huì)把我最近寫的算法都發(fā)表在這里，希望大家喜歡，共同進(jìn)步~
2010年8月21日
摘要: 1000 A+B Problem 送分題1001 Exponentiation ...
閱讀全文
貪心算法，使用STL的priority_queue來維護(hù)一個(gè)隊(duì)列。保證魚數(shù)最多（相同魚則保存標(biāo)號(hào)較小的）的一個(gè)序列。然后貪心就可以了。一下是代碼
#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];
}
///////////數(shù)據(jù)輸入完畢，開始進(jìn)入計(jì)算
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;
}
2010年8月20日
回溯法:八皇后問題，一個(gè)經(jīng)典問題
在程序設(shè)計(jì)中還有一種方法叫做"回溯法".他不是按照某種公式或確定的法則,求問題的解,而是通過試探和糾正錯(cuò)誤的策略,找到問題的街.這種方法一般是從一個(gè)原始狀態(tài)出發(fā),通過若干步試探,最后達(dá)到目標(biāo)狀態(tài)終止.
回溯法在理論上來說,就是在一棵搜索樹中從根結(jié)點(diǎn)出發(fā),找到一條達(dá)到滿足某條件的子結(jié)點(diǎn)的路徑.在搜索過程中,對(duì)于每一個(gè)中間結(jié)點(diǎn),他的位置以及向下搜索過程是相似的,因此完全可以用遞歸來處理.典型的例子就是著名的"八皇后問題".
"八皇后問題"是在國際象棋棋盤上放置八個(gè)皇后,使她們不能相吃.國際象棋中的皇后可以吃掉與她處于同一行,同一列,同一對(duì)角線上的棋子.因此每一行只能擺放一個(gè)皇后.因共有八行,所以每行有且只有一個(gè)皇后.
在本例中皇后的位置有一個(gè)一維數(shù)組來存放A(I)=J表示第I行皇后放在第J列.下面主要來看看怎么樣判斷皇后是否安全的問題.(1)首先,用一維數(shù)組來表示,已經(jīng)解決了不在同一行的問題.(2)對(duì)于列可以引進(jìn)一個(gè)標(biāo)志數(shù)組C[J],若J列上已放了皇后,則C[J]=FALSE.(3)對(duì)于左上右下的對(duì)角線I-J為一常量,位于[-7,+7]之間,再此引入標(biāo)志數(shù)組L[-7..7];對(duì)于左下右上的對(duì)角線,類似的有I+J等于常量,用數(shù)組R[2..16]來表示.當(dāng)在第I行,第J列上放置了皇后,則只需設(shè)置:C[J]:=FALSE; L[I-J]:=FLASE; R[I+J]:=FALSE就可以解決皇后的安全問題了.
問題描述：在標(biāo)準(zhǔn)國際象棋的棋盤上（8*8格）準(zhǔn)備放置8只皇后，我們知道，國際象棋中皇后的威力是最大的，她既可以橫走豎走，還可以斜著走，遇到擋在她前進(jìn)路線上的敵人，她就可以吃掉對(duì)手。要求在棋盤上安放8只皇后，使她們彼此互相都不能吃到對(duì)方，求皇后的放法。
/************************************************************************/
/* */
/* 問題：在8×8的國際象棋棋盤上放置8個(gè)皇后，要求任意兩個(gè)皇后 */
/* 不能在同一行、同一列或同一條對(duì)角線上。 */
/* */
/* 本程序使用遞歸－回溯法求解8皇后問題。Visual C++ 6.0 調(diào)試通過。 */
/* 作者 晨星 2002年5月9日 */
/* */
/************************************************************************/
#include <stdio.h>
#include <conio.h>
#include <math.h>
#define QUEENS 8
//!記錄解的序號(hào)的全局變量。
int iCount = 0;
//!記錄皇后在各列上的放置位置的全局?jǐn)?shù)組。
int Site[QUEENS];
//!遞歸求解的函數(shù)。
void Queen(int n);
//!輸出一個(gè)解。
void Output();
//!判斷第n個(gè)皇后放上去之后，是否有沖突。
int IsValid(int n);
/*----------------------------Main：主函數(shù)。 ----------------------------*/
void main()
{
//!從第0列開始遞歸試探。
Queen(0);
//!按任意鍵返回。
getch();
}
/*-----------------Queen：遞歸放置第n個(gè)皇后，程序的核心!----------------*/
void Queen(int n)
{
int i;
//!參數(shù)n從0開始，等于8時(shí)便試出了一個(gè)解，將它輸出并回溯。
if(n == QUEENS)
{
Output();
return;
}
//!n還沒到8，在第n列的各個(gè)行上依次試探。
for(i = 1 ; i <= QUEENS ; i++)
{
//!在該列的第i行上放置皇后。
Site[n] = i;
//!如果放置沒有沖突，就開始下一列的試探。
if(IsValid(n))
Queen(n + 1);
}
}
/*------IsValid：判斷第n個(gè)皇后放上去之后，是否合法，即是否無沖突。------*/
int IsValid(int n)
{
int i;
//!將第n個(gè)皇后的位置依次于前面n－1個(gè)皇后的位置比較。
for(i = 0 ; i < n ; i++)
{
//!兩個(gè)皇后在同一行上，返回0。
if(Site[i] == Site[n])
return 0;
//!兩個(gè)皇后在同一對(duì)角線上，返回0。
if(abs(Site[i] - Site[n]) == (n - i))
return 0;
}
//!沒有沖突，返回1。
return 1;
}
/*------------Output：輸出一個(gè)解，即一種沒有沖突的放置方案。------------*/
void Output()
{
int i;
//!輸出序號(hào)。
printf("No.%-5d" , ++iCount);
//!依次輸出各個(gè)列上的皇后的位置，即所在的行數(shù)。
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);
}
遞歸解八皇后問題
/*遞歸法解八皇后問題*/
/*作者黃國瑜，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》清華大學(xué)出版社*/
char Chessboard[8][8]; /*聲明8＊8的空白棋盤*/
int N_Queens(int LocX, int LocY, int Queens) /*遞歸*/
{
int i,j;
int Result=0;
if(Queens == 8)/*遞歸結(jié)束條件*/
return 1;
else if(QueenPlace(LocX,LocY))/*遞歸執(zhí)行部分*/
{
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) /*判斷傳入坐標(biāo)本身及入八個(gè)方向上是否有皇后*/
{
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();
}
/*********************************************************
*****************八皇后問題*******************************
************根據(jù)嚴(yán)書給的類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 一定要設(shè)為內(nèi)部變量*/
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; /*對(duì)角*/
while((p>=0)&&(q>=0))
{
if(a[p][q]==1)
{
bslash=0;
break;
}
p--;
q--;
} /*斜對(duì)角*/
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();
}
這是一個(gè)全排列算法的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;//序號(hào)
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;//當(dāng)N為8時(shí)耗時(shí)130秒，與泛型算法next_permutation用時(shí)一樣
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;
}
2010年8月19日
大整數(shù)的加法。與以前高精度算法不同的是這次要一下子讀入一個(gè)算式。然后簡便的是，這次不用再交換順序了，直接加。但是結(jié)果的判斷稍微麻煩一點(diǎn)，要把開頭的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;
}