針對一個已經被排序好的數列,
用二分搜尋法半均只要執行Log2N次,
就可以找到你要的數字。
#include<stdio.h>
#include<stdlib.h>
int to=0 ;
void go(int a[],int st,int ed,int goal) //引數有:一串數字、左界、右界、要找的數字
{
int h=(ed+st)/2 ;
if(ed-st>1)
{
if(a[h]>goal)
{
to+=1 ;
go(a,st,h-1,goal) ; 數字太大,就往小的一方找。
}
else if(a[h]<goal)
{
to+=1 ;
go(a,h+1,ed,goal) ; 數字太小,就往大的一方找。
}
else
{
printf("a[%d] = %d(%d)\t",h,goal,to) ;
}
}
else
{
if(a[st]==goal)printf("a[%d] = %d(%d)\t",st,goal,to) ;
else if(a[ed]==goal) printf("a[%d] = %d(%d)\t",ed,goal,to) ;
else printf("Fail\n") ;
}
}
int main()
{
int a[100],kk=0 ;
for(int k=0;k<100;k++){a[k]=k ;printf("%d \t",a[k]) ;} //在這裡,我們把0~99都找過一次。
printf("\n") ;
for(kk=0;kk<100;kk++)
{
to=1 ;
go(a,0,99,kk) ;
}
system("pause") ;
return 0 ;
}
2012年5月26日 星期六
2012年5月25日 星期五
C# -> 走迷宮程式
這裡有一座迷宮......
<Start>
##############
#A #
####### ######
# #
## ######## ##
# #
##############
<Next>
<End>
'A'代表你的位置,'#'代表牆壁,空白處代表可以走的路。
邊邊有一格是空白的,那就是出口。
現在我們要做的事,就是看看你如何走出這個迷宮。
我們在這邊要用到一個演算法 - BFS(廣度優先搜索)
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
char map[101][101],spp[101] ;
int dis[101][101],sp[101][101] ;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0} ;
int n=0,m=0,i=0,j=0,k=0,pass=0,to=0,noway=0,nw_count=0 ;
void prt(void) //把當前得地圖狀態列印出來
{
printf("No.%d >>\n",to) ;
for(int ix=0;ix<n;ix++){
for(int jx=0;map[ix][jx]!='\0';jx++){
if(sp[ix][jx]==1)
printf("%c",'A') ;
else if(sp[ix][jx]==2 || map[ix][jx]=='.')
printf("%c",' ') ;
else
printf("%c",'#') ;
}
printf("\n") ;
}
for(int ix=0;ix<22-n;ix++)printf("\n") ;
getch() ;
}
int main()
{
FILE *fp ;
fp=fopen("data.txt","r") ;//在這裡我們用讀取txt檔的方式來輸入資料,因為迷宮可能會有很多座
while(fscanf(fp,"%s",spp)!=EOF){
if(spp[1]=='E')break ;
else if(spp[1]=='S'){ //如果是<START>那麼就把迷宮讀入
for(i=0;i<101;i++)
for(j=0;j<101;j++)map[i][j]='\0' ;
for(m=0;;m++){
fscanf(fp,"%s",map[m]) ;
if(map[m][1]=='N'){ //如果是<NEXT>那麼就開始分析迷宮,並解開。
n=m;
for(i=0;map[m][i]!='\0';map[m][i++]='\0');
break;
}
}
}
for(i=0;i<n;i++){
for(j=0;map[i][j]!='\0';j++){
dis[i][j]=sp[i][j]=0 ;
if(map[i][j]=='A')sp[i][j]=1 ; //標記你的位置
}
}
to=noway=pass=0 ;
while(!pass)
{
prt() ;
for(i=0;i<n;i++){
for(j=0;map[i][j]!='\0';j++){
if(sp[i][j]==1){ //如果你走過,就看看上、下、左、右是否還有路或沒走過的路要走。
for(k=0;k<4;k++){
if(map[i+dy[k]][j+dx[k]]=='.'){ //我們用'.'來代替space
if(!sp[i+dy[k]][j+dx[k]]){
sp[i+dy[k]][j+dx[k]]=-1 ;
dis[i+dy[k]][j+dx[k]]=dis[i][j]+1 ;
to=dis[i][j]+1 ;
}
}
else if(map[i+dy[k]][j+dx[k]]=='\0' || !i || !j){
pass=1 ;
to=dis[i][j] ;
break ;
}
}
sp[i][j]=2 ;
}
if(pass)break ;
}
if(pass)break ;
}
if(!pass)noway=1 ;
for(i=0;i<n;i++){
for(j=0;map[i][j]!='\0';j++){
if(sp[i][j]==-1){
sp[i][j]=1 ;
noway=0 ;
}
}
}
if(!pass)pass=noway ;
}
if(!noway){
printf("%d Steps\n",to) ; //找到出路! 列印出你走了幾步。
}
else{
printf("走不出去啊!\n你耍我!?\n") ; //所有路都走過了,可是就是走不出去> <!
}
getch() ;
}
printf("THE END\n") ;
getch() ;
return 0 ;
}
BFS 的功能可是很強大的呢!
在此,只是介紹它一部分的力量。
希望大家會喜歡。
2012年5月24日 星期四
C# -> 解數獨
想要解數獨,通常是用「試誤法」,就是一格一格試
若不符合,則退一格再試,一直試到結束。
#include<stdio.h>
#include<stdlib.h>
int sodoku[10][10],post[10][10][2],cnt[82],blank[82][2] ; //sodoku是數獨表,post[i][j][0 or 1]記錄第(i,j)格屬於的宮的開頭坐標,cnt[i]是指第i個未知數目前被嘗試放入的數字,blank[i][0 or 1]分別代表待解之數的x和y坐標
int n,i,j,k,kx,ky,index,to,pass,fin ;
int pos(int x,int y) ;
int chk(int x,int y) ;
void prt(void) ;
int pos(int x,int y){
int xy = 0 ;
if(x <= n){
xy = 10 ;
}else if(n == 2){
xy = 30 ;
}else if(n == 3){
if(x > n * 2)xy = 70 ;
else xy = 40 ;
}
if(y <= n){
xy += 1 ;
}else if(n == 2){
xy += 3 ;
}else if(n == 3){
if(y > n * 2)xy += 7 ;
else xy += 4 ;
}
return xy ;
}
int chk(int x,int y){ //檢查目前的sodoku是否合法
int ix,iy ;
for(ix = 1 ; ix <= n * n ; ix++){
if(ix != x && sodoku[ix][y] == sodoku[x][y])return 0 ;
}
for(iy = 1 ; iy <= n * n ; iy++){
if(iy != y && sodoku[x][iy] == sodoku[x][y])return 0 ;
}
for(ix = post[x][y][0] ; ix < post[x][y][0] + n ; ix++){
for(iy = post[x][y][1] ; iy < post[x][y][1] + n ; iy++){
if(ix != x && iy != y && sodoku[ix][iy] == sodoku[x][y])return 0 ;
}
}
return 1 ;
}
void prt(void){
int ix,iy ;
for(ix = 1 ; ix <= n * n ; ix++){
for(iy = 1 ; iy <= n * n ; iy++){
printf("%d ",sodoku[ix][iy]) ;
}
printf("\n") ;
}
printf("\n") ;
//system("pause") ;
}
int main()
{
while(scanf("%d",&n)!=EOF){
to = index = 0 ;
for(i = 1 ; i <= n * n ; i++) //先讀資料(在此只考慮n<=3的情況)
for(j = 1 ; j <= n * n ; j++){
scanf("%d",&sodoku[i][j]) ;
if(!sodoku[i][j]){ // 若讀到0,則表示這格是待解的數
blank[to][0] = i ;
blank[to][1] = j ;
to += 1 ;
}
}
for(i = 1 ; i <= n * n ; i++){//記錄第i列第j行是屬於哪一宮(以n=3來說,就是指九宮格)
for(j = 1 ; j <= n * n ; j++){
post[i][j][0] = pos(i,j) / 10 ;
post[i][j][1] = pos(i,j) % 10 ;
}
}
pass = 1 ;
for(i = 1 ; i <= n * n ; i++){
for(j = 1 ; j <= n * n ; j++){
if(sodoku[i][j]){
if(!chk(i,j)){
pass = 0 ;
break ;
}
}
}
if(!pass)break ;
}
if(!pass){
printf("NO SOLUTION\n") ;
}else{
cnt[0] = 0 ;
for(index = 0;;){ //開始一個一個跑
if(cnt[index] < n * n){
cnt[index] += 1 ;
sodoku[blank[index][0]][blank[index][1]] = cnt[index] ;
if(chk(blank[index][0],blank[index][1])){
if(index < to - 1){
index += 1 ;
cnt[index] = 0 ;
}else{
prt() ; //找到了,print出來
fin = 1 ;
break ;
}
}
}else{
if(!index){
if(!fin)printf("NO SOLUTION\n") ; //找不到,輸出NO SOLUTION
break ;
}else{
sodoku[blank[index][0]][blank[index][1]] = 0 ;
index -= 1 ;
}
}
} //for(index;;)的右中括號
} //if(!pass)的右中括號
} //while(scanf("%d",&n)!=EOF)的右中括號
//system("pause") ;
return 0 ;
}
全部都是未知數的話,找到一組字典順序在最前面的。
若不符合,則退一格再試,一直試到結束。
#include<stdio.h>
#include<stdlib.h>
int sodoku[10][10],post[10][10][2],cnt[82],blank[82][2] ; //sodoku是數獨表,post[i][j][0 or 1]記錄第(i,j)格屬於的宮的開頭坐標,cnt[i]是指第i個未知數目前被嘗試放入的數字,blank[i][0 or 1]分別代表待解之數的x和y坐標
int n,i,j,k,kx,ky,index,to,pass,fin ;
int pos(int x,int y) ;
int chk(int x,int y) ;
void prt(void) ;
int pos(int x,int y){
int xy = 0 ;
if(x <= n){
xy = 10 ;
}else if(n == 2){
xy = 30 ;
}else if(n == 3){
if(x > n * 2)xy = 70 ;
else xy = 40 ;
}
if(y <= n){
xy += 1 ;
}else if(n == 2){
xy += 3 ;
}else if(n == 3){
if(y > n * 2)xy += 7 ;
else xy += 4 ;
}
return xy ;
}
int chk(int x,int y){ //檢查目前的sodoku是否合法
int ix,iy ;
for(ix = 1 ; ix <= n * n ; ix++){
if(ix != x && sodoku[ix][y] == sodoku[x][y])return 0 ;
}
for(iy = 1 ; iy <= n * n ; iy++){
if(iy != y && sodoku[x][iy] == sodoku[x][y])return 0 ;
}
for(ix = post[x][y][0] ; ix < post[x][y][0] + n ; ix++){
for(iy = post[x][y][1] ; iy < post[x][y][1] + n ; iy++){
if(ix != x && iy != y && sodoku[ix][iy] == sodoku[x][y])return 0 ;
}
}
return 1 ;
}
void prt(void){
int ix,iy ;
for(ix = 1 ; ix <= n * n ; ix++){
for(iy = 1 ; iy <= n * n ; iy++){
printf("%d ",sodoku[ix][iy]) ;
}
printf("\n") ;
}
printf("\n") ;
//system("pause") ;
}
int main()
{
while(scanf("%d",&n)!=EOF){
to = index = 0 ;
for(i = 1 ; i <= n * n ; i++) //先讀資料(在此只考慮n<=3的情況)
for(j = 1 ; j <= n * n ; j++){
scanf("%d",&sodoku[i][j]) ;
if(!sodoku[i][j]){ // 若讀到0,則表示這格是待解的數
blank[to][0] = i ;
blank[to][1] = j ;
to += 1 ;
}
}
for(i = 1 ; i <= n * n ; i++){//記錄第i列第j行是屬於哪一宮(以n=3來說,就是指九宮格)
for(j = 1 ; j <= n * n ; j++){
post[i][j][0] = pos(i,j) / 10 ;
post[i][j][1] = pos(i,j) % 10 ;
}
}
pass = 1 ;
for(i = 1 ; i <= n * n ; i++){
for(j = 1 ; j <= n * n ; j++){
if(sodoku[i][j]){
if(!chk(i,j)){
pass = 0 ;
break ;
}
}
}
if(!pass)break ;
}
if(!pass){
printf("NO SOLUTION\n") ;
}else{
cnt[0] = 0 ;
for(index = 0;;){ //開始一個一個跑
if(cnt[index] < n * n){
cnt[index] += 1 ;
sodoku[blank[index][0]][blank[index][1]] = cnt[index] ;
if(chk(blank[index][0],blank[index][1])){
if(index < to - 1){
index += 1 ;
cnt[index] = 0 ;
}else{
prt() ; //找到了,print出來
fin = 1 ;
break ;
}
}
}else{
if(!index){
if(!fin)printf("NO SOLUTION\n") ; //找不到,輸出NO SOLUTION
break ;
}else{
sodoku[blank[index][0]][blank[index][1]] = 0 ;
index -= 1 ;
}
}
} //for(index;;)的右中括號
} //if(!pass)的右中括號
} //while(scanf("%d",&n)!=EOF)的右中括號
//system("pause") ;
return 0 ;
}
全部都是未知數的話,找到一組字典順序在最前面的。
2012年5月23日 星期三
C# -> 質因數分解
通常,分解質因數,我們會先建立一張質數表。
然後,再從最小的質數 2 開始,逐個判斷是否可以整除該數。
C# code :
#include<stdio.h>
#include<stdlib.h>
int pri[1000],co[1000] ; //pri[i] 為第i小的質數,co[i] 為n之中有多少 pri[i]次方
int n=0,i=0,j=0,k=0,pass=0,to=0,f=0 ;
int main()
{
//質數表
pri[0]=2 ;
pri[1]=3 ;
to=2 ;
for(i=5;i<=1000;i+=2){
pass=1 ;
for(j=0;j<to;j++){
if(!(i%pri[j])){pass=0;break;}
}
if(pass){
pri[to++]=i ;
}
}
//質因數分解
while(scanf("%d",&n)!=EOF){
for(i=0;i<to;i++)co[i]=0 ;
for(i=0;i<to;i++){
while(!(n%pri[i])){ //判斷某個質數是否可以整除 n ,直到不能在除為止。
co[i]+=1 ;
n/=pri[i] ;
}
}
f=0 ;
for(i=0;i<to;i++){ //列印
if(co[i]){
if(f)printf(" * ") ;
else f=1 ;
if(co[i]==1){
printf("%d",pri[i]) ;
}
else {
printf("%d^%d",pri[i],co[i]) ;
}
}
}
if(n>1){
if(f)printf(" * ") ;
printf("%d\n",n) ;
}
else printf("\n") ;
}
return 0 ;
}
然後,再從最小的質數 2 開始,逐個判斷是否可以整除該數。
C# code :
#include<stdio.h>
#include<stdlib.h>
int pri[1000],co[1000] ; //pri[i] 為第i小的質數,co[i] 為n之中有多少 pri[i]次方
int n=0,i=0,j=0,k=0,pass=0,to=0,f=0 ;
int main()
{
//質數表
pri[0]=2 ;
pri[1]=3 ;
to=2 ;
for(i=5;i<=1000;i+=2){
pass=1 ;
for(j=0;j<to;j++){
if(!(i%pri[j])){pass=0;break;}
}
if(pass){
pri[to++]=i ;
}
}
//質因數分解
while(scanf("%d",&n)!=EOF){
for(i=0;i<to;i++)co[i]=0 ;
for(i=0;i<to;i++){
while(!(n%pri[i])){ //判斷某個質數是否可以整除 n ,直到不能在除為止。
co[i]+=1 ;
n/=pri[i] ;
}
}
f=0 ;
for(i=0;i<to;i++){ //列印
if(co[i]){
if(f)printf(" * ") ;
else f=1 ;
if(co[i]==1){
printf("%d",pri[i]) ;
}
else {
printf("%d^%d",pri[i],co[i]) ;
}
}
}
if(n>1){
if(f)printf(" * ") ;
printf("%d\n",n) ;
}
else printf("\n") ;
}
return 0 ;
}
2012年5月18日 星期五
C# -> 窮舉子集
如果有一個集合S = {0,1,2}
則S的所有子集為 :
1 : { }
2 : { 0 }
3 : { 1 }
4 : { 0 1 }
5 : { 2 }
則S的所有子集為 :
1 : { }
2 : { 0 }
3 : { 1 }
4 : { 0 1 }
5 : { 2 }
6 : { 0 2 }
7 : { 1 2 }
8 : { 0 1 2 }
我們可以用二進位的特性來實現...
以上例來說...從0~2^3 - 1的二進位制依序是...
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
000 可以看成0,1,2都不選,就是空集合
001 可以看成取0
......
111 可以看成0,1,2都選,就是S
C# code :
以上例來說...從0~2^3 - 1的二進位制依序是...
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
000 可以看成0,1,2都不選,就是空集合
001 可以看成取0
......
111 可以看成0,1,2都選,就是S
C# code :
#include<stdio.h>
#include<stdlib.h>
int i=0,j=0,t=0,n=0 ;
void subsets(int n)
{
for (i=0;i<(1<<n);i++) //利用位元運算從0 ~ 2^n - 1
{
printf("%d : { ",i) ;
for (j=0,t=i;j<=n;j++,t>>=1)
if (t&1)
printf("%d ",j) ;
printf("}\n") ;
}
}
int main()
{
printf("Please enter a number which is smaller than 31\n") ;
while(1)
{
n=31 ;
while(n>30)scanf("%d",&n) ;
subsets (n) ;
printf("**********************************************\n") ;
}
//system("pause") ;
return 0 ;
}
其中subsets,就是窮舉子集的函式。
2012年4月20日 星期五
訂閱:
文章 (Atom)