[心得] //0.004
在西洋棋得棋盤中你可以放置8個皇后而且彼此都不衝突（就是都不能吃到對方）。給你某一個皇后的位置，請你寫一個程式來輸出所有這樣可能的安排。
#include <stdio.h>
#define MAXSIZE 8
int map[MAXSIZE+1],left[2*MAXSIZE+1],right[2*MAXSIZE+1],answer[MAXSIZE+1];
int a,b;
int counter;
void queen(int x)
{
int i;
if(x == b)
++x;
if(x==9)
{
printf( "%2d ", ++counter );
for ( i = 1; i <= MAXSIZE; i++ )
{
printf( " %d", answer[ i ] );
}
printf("\n");
return;
}
for(i = 1; i <= MAXSIZE;i++)
{
int L = i-x+MAXSIZE;
int R = i+x;
if(!left[L]&&!right[R]&& !map[i])
{
left[L] = right[R]=map[i]=1;
answer[x]=i;
queen(x+1);
left[L] = right[R]=map[i]=0;
}
}
}
int main()
{
int data;
scanf("%d",&data);
while(data--)
{
scanf("%d %d",&a,&b);
memset(map, 0, sizeof(int)*(MAXSIZE+1));
memset(left, 0, sizeof(int)*(2*MAXSIZE+1));
memset(right,0, sizeof(int)*(2*MAXSIZE+1));
left[a-b+MAXSIZE]=1;
right[a+b]=1;
map[a]=1;
answer[b]=a;
counter = 0;
printf( "SOLN COLUMN\n # 1 2 3 4 5 6 7 8\n\n" );
queen(1);
if(data )
printf("\n");
}
//return 0;
system("pause");
}
2011年12月31日 星期六
C stake (struct)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 10
typedef struct
{
int item[MAXSIZE];
int top;
}Stack;
bool is_full(Stack s)
{
return (s.top ==(MAXSIZE -1));
}
bool is_empty(Stack s)
{
return (s.top == -1);
}
Stack create(Stack s)
{
s.top =-1;
return s;
}
Stack push(Stack s ,int key)
{
if(is_full(s))
printf("Stack is Full\n");
else{
s.top=s.top+1;
s.item[s.top] = key;
}
return s;
}
Stack pop(Stack s)
{
if(is_empty(s))
printf("Stack is empty");
else
{
s.item[s.top]=0;
s.top= s.top-1;
}
return s;
}
void display(Stack s)
{
int i;
for(i=0;i<=s.top;i++)
printf("item[%d]=%d\n",i,s.item[i]);
}
int main()
{
Stack s;
s= create(s);
int key;
int choice;
printf("--------------------------------\n");
printf("1.push:\n");
printf("2.pop:\n");
printf("3.display stack\n");
printf("--------------------------------\n");
do{
printf("Enter the function number>");
scanf("%d",&choice);
if(choice == 1){
printf("please input a number to push :\n");
scanf("%d",&key);
s=push(s,key);
}
else if(choice == 2)
s=pop(s);
else if(choice == 3)
display(s);
}while(choice != -1);
system("pause");
}
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 10
typedef struct
{
int item[MAXSIZE];
int top;
}Stack;
bool is_full(Stack s)
{
return (s.top ==(MAXSIZE -1));
}
bool is_empty(Stack s)
{
return (s.top == -1);
}
Stack create(Stack s)
{
s.top =-1;
return s;
}
Stack push(Stack s ,int key)
{
if(is_full(s))
printf("Stack is Full\n");
else{
s.top=s.top+1;
s.item[s.top] = key;
}
return s;
}
Stack pop(Stack s)
{
if(is_empty(s))
printf("Stack is empty");
else
{
s.item[s.top]=0;
s.top= s.top-1;
}
return s;
}
void display(Stack s)
{
int i;
for(i=0;i<=s.top;i++)
printf("item[%d]=%d\n",i,s.item[i]);
}
int main()
{
Stack s;
s= create(s);
int key;
int choice;
printf("--------------------------------\n");
printf("1.push:\n");
printf("2.pop:\n");
printf("3.display stack\n");
printf("--------------------------------\n");
do{
printf("Enter the function number>");
scanf("%d",&choice);
if(choice == 1){
printf("please input a number to push :\n");
scanf("%d",&key);
s=push(s,key);
}
else if(choice == 2)
s=pop(s);
else if(choice == 3)
display(s);
}while(choice != -1);
system("pause");
}
C stack (struct linklist)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 10
typedef struct Stack {
int data;
struct Stack *link;
}Stack;
struct Stack *top =NULL;
struct Stack *tmp =NULL;
struct Stack *current =NULL;
struct Stack push(Stack s,int key)
{
tmp = (struct Stack *)malloc(sizeof(struct Stack));
tmp->data= key;
tmp->link =top;
top=tmp;
return s;
}
struct Stack pop(Stack s)
{
if(top==NULL)
printf("no data\n");
else
{
tmp =top;
top =top->link;
free(tmp);
return s;
}
}
struct Stack display(Stack s)
{
current = (struct Stack *)malloc(sizeof(struct Stack));
current =top;
if(current==NULL)
printf("no data\n");
else
{
while(current != NULL)
{
printf("%d \n",current->data);
current=current->link;
}
}
}
int main()
{
Stack s;
//s= create(s);
int key;
int choice;
printf("--------------------------------\n");
printf("1.push:\n");
printf("2.pop:\n");
printf("3.display stack\n");
printf("--------------------------------\n");
do{
printf("Enter the function number>");
scanf("%d",&choice);
if(choice == 1){
printf("please input a number to push :\n");
scanf("%d",&key);
s=push(s,key);
}
else if(choice == 2){
printf("choice == 2\n");
s=pop(s);
}
else if(choice == 3)
display(s);
}while(choice != -1);
system("pause");
}
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 10
typedef struct Stack {
int data;
struct Stack *link;
}Stack;
struct Stack *top =NULL;
struct Stack *tmp =NULL;
struct Stack *current =NULL;
struct Stack push(Stack s,int key)
{
tmp = (struct Stack *)malloc(sizeof(struct Stack));
tmp->data= key;
tmp->link =top;
top=tmp;
return s;
}
struct Stack pop(Stack s)
{
if(top==NULL)
printf("no data\n");
else
{
tmp =top;
top =top->link;
free(tmp);
return s;
}
}
struct Stack display(Stack s)
{
current = (struct Stack *)malloc(sizeof(struct Stack));
current =top;
if(current==NULL)
printf("no data\n");
else
{
while(current != NULL)
{
printf("%d \n",current->data);
current=current->link;
}
}
}
int main()
{
Stack s;
//s= create(s);
int key;
int choice;
printf("--------------------------------\n");
printf("1.push:\n");
printf("2.pop:\n");
printf("3.display stack\n");
printf("--------------------------------\n");
do{
printf("Enter the function number>");
scanf("%d",&choice);
if(choice == 1){
printf("please input a number to push :\n");
scanf("%d",&key);
s=push(s,key);
}
else if(choice == 2){
printf("choice == 2\n");
s=pop(s);
}
else if(choice == 3)
display(s);
}while(choice != -1);
system("pause");
}
2011年12月30日 星期五
C linklist -練習
[心得] : 1.注意反轉.與delete
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char input_name[255];
int input_age;
struct Node{
char name[255];
int age;
struct Node *next;
};
struct Node *first=NULL;
struct Node *temp=NULL;
struct Node *current=NULL;
void EnterData()
{
printf("please input name :");
scanf("%s",&input_name);
printf("please input age :");
scanf("%d",&input_age);
}
void CreateFirstNode(int input_age,char* input_name)
{
first = (struct Node *)malloc(sizeof(struct Node));
strcpy(first->name,input_name);
first->age =input_age;
current =first;
current->next =NULL;
}
void InsertNode(int input_age,char *input_name)
{
temp=(struct Node*)malloc(sizeof(struct Node));
temp->age =input_age;
strcpy(temp->name,input_name);
temp->next =NULL;
current->next =temp;
current =temp;
}
void deleteNode(char* input_name)
{
struct Node *temp_prev=NULL;
temp =first;
if(temp ==NULL)
printf("NO data to delete");
while(temp!=NULL)
{
if(strcmp(first->name,input_name)==0)
{
first = temp->next;
free(temp);
}
if(strcmp(temp->name,input_name)==0)
{
temp_prev->next =temp->next; //要先把欲刪除的Node_B(temp)的前一個Node_A(temp_prev-)指到B的後面一個Node_C(temp->next)
free(temp);
}
temp_prev=temp;//這兩行指再繼續下一個點
temp=temp->next;
}
}
void display()
{
temp =first;
if(first==NULL)
printf("NO data");
else
{
while(temp!=NULL)
{
printf("name = %s, age = %d \n",temp->name,temp->age);
temp =temp->next;
}
}
}
void Invert_linklist()
{
struct Node *p=NULL;
p=first;
temp=NULL;
while(first->next != NULL)
{
first = p->next; //先把first assign到下一個點
p->next = temp; //p再指回去前面的點
temp=p; //再繼續反轉下一個點
p=first;
}
p->next =temp; //這行很重要,要記得最後要再把p下一個點,指到temp
}
void selsectFun()
{
int i;
printf("------------------------------------\n");
printf("|1 Add Node\n");
printf("|2 Delete Node\n");
printf("|3 Display List Node\n");
printf("|4 Display and Invert List Node\n");
printf("|-1 Exit\n");
printf("------------------------------------\n");
do
{
printf("Enter the function number>");
scanf("%d",&i);
if(i == 1)
{
if(first == NULL)
{
EnterData();
CreateFirstNode(input_age,input_name);
}
else
{
EnterData();
InsertNode(input_age,input_name);
}
}
else if(i == 2)
{
printf("Enter the person's name>");
scanf("%s",&input_name);
deleteNode(input_name);
}
else if(i == 3)
display();
else if(i == 4) {
Invert_linklist();
display();
}
else if(i == -1)
{}
else
printf("Wrong function number!!\n");
}while(i != -1);
}
int main()
{
selsectFun();
system("pause");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char input_name[255];
int input_age;
struct Node{
char name[255];
int age;
struct Node *next;
};
struct Node *first=NULL;
struct Node *temp=NULL;
struct Node *current=NULL;
void EnterData()
{
printf("please input name :");
scanf("%s",&input_name);
printf("please input age :");
scanf("%d",&input_age);
}
void CreateFirstNode(int input_age,char* input_name)
{
first = (struct Node *)malloc(sizeof(struct Node));
strcpy(first->name,input_name);
first->age =input_age;
current =first;
current->next =NULL;
}
void InsertNode(int input_age,char *input_name)
{
temp=(struct Node*)malloc(sizeof(struct Node));
temp->age =input_age;
strcpy(temp->name,input_name);
temp->next =NULL;
current->next =temp;
current =temp;
}
void deleteNode(char* input_name)
{
struct Node *temp_prev=NULL;
temp =first;
if(temp ==NULL)
printf("NO data to delete");
while(temp!=NULL)
{
if(strcmp(first->name,input_name)==0)
{
first = temp->next;
free(temp);
}
if(strcmp(temp->name,input_name)==0)
{
temp_prev->next =temp->next; //要先把欲刪除的Node_B(temp)的前一個Node_A(temp_prev-)指到B的後面一個Node_C(temp->next)
free(temp);
}
temp_prev=temp;//這兩行指再繼續下一個點
temp=temp->next;
}
}
void display()
{
temp =first;
if(first==NULL)
printf("NO data");
else
{
while(temp!=NULL)
{
printf("name = %s, age = %d \n",temp->name,temp->age);
temp =temp->next;
}
}
}
void Invert_linklist()
{
struct Node *p=NULL;
p=first;
temp=NULL;
while(first->next != NULL)
{
first = p->next; //先把first assign到下一個點
p->next = temp; //p再指回去前面的點
temp=p; //再繼續反轉下一個點
p=first;
}
p->next =temp; //這行很重要,要記得最後要再把p下一個點,指到temp
}
void selsectFun()
{
int i;
printf("------------------------------------\n");
printf("|1 Add Node\n");
printf("|2 Delete Node\n");
printf("|3 Display List Node\n");
printf("|4 Display and Invert List Node\n");
printf("|-1 Exit\n");
printf("------------------------------------\n");
do
{
printf("Enter the function number>");
scanf("%d",&i);
if(i == 1)
{
if(first == NULL)
{
EnterData();
CreateFirstNode(input_age,input_name);
}
else
{
EnterData();
InsertNode(input_age,input_name);
}
}
else if(i == 2)
{
printf("Enter the person's name>");
scanf("%s",&input_name);
deleteNode(input_name);
}
else if(i == 3)
display();
else if(i == 4) {
Invert_linklist();
display();
}
else if(i == -1)
{}
else
printf("Wrong function number!!\n");
}while(i != -1);
}
int main()
{
selsectFun();
system("pause");
return 0;
}
C ACM 488 Triangle Wave
[心得] : //runtime 0.468
1.再第四各for迴圈裡
for(i=0;i
{
for(j=0;j
printf("%d",i);
if(i!=0) printf("\n");
}
因為i 是從0開始計算,所以第一次j=0時, 條件不成立 ,會多印一次printf("\n"); 所以只好加上
if(i!=0) printf("\n"); 判斷
2. if(!((k==b[h]-1)&&(h==s-1))) printf("\n"); 題目規定最後輸出不需換行
#include <stdio.h>
#include <stdlib.h>
int main()
{
int s;
int a[100],b[100];
int m =0;
int i,j,k,l,h;
scanf("%d",&s);
for(h=0;h<s;h++)
scanf("%d %d",&a[h],&b[h]);
for(h=0;h<s;h++)
{
for(k=0;k<b[h];k++)
{
for(i=0;i<=a[h];i++)
{
for(j=0;j<i;j++)
printf("%d",i);
if(i!=0) printf("\n");
}
for(l=a[h]-1;l>=1;l--)
{
for(i=0;i<l;i++)
printf("%d",l);
printf("\n");
}
if(!((k==b[h]-1)&&(h==s-1))) printf("\n");
}
}
system("pause");
//return 0;
}
1.再第四各for迴圈裡
for(i=0;i
{
for(j=0;j
printf("%d",i);
if(i!=0) printf("\n");
}
因為i 是從0開始計算,所以第一次j=0時, 條件不成立 ,會多印一次printf("\n"); 所以只好加上
if(i!=0) printf("\n"); 判斷
2. if(!((k==b[h]-1)&&(h==s-1))) printf("\n"); 題目規定最後輸出不需換行
#include <stdio.h>
#include <stdlib.h>
int main()
{
int s;
int a[100],b[100];
int m =0;
int i,j,k,l,h;
scanf("%d",&s);
for(h=0;h<s;h++)
scanf("%d %d",&a[h],&b[h]);
for(h=0;h<s;h++)
{
for(k=0;k<b[h];k++)
{
for(i=0;i<=a[h];i++)
{
for(j=0;j<i;j++)
printf("%d",i);
if(i!=0) printf("\n");
}
for(l=a[h]-1;l>=1;l--)
{
for(i=0;i<l;i++)
printf("%d",l);
printf("\n");
}
if(!((k==b[h]-1)&&(h==s-1))) printf("\n");
}
}
system("pause");
//return 0;
}
C about char 0X80
[心得]
unsigned char 型別定義為 範圍從 0 至256
char 型別定義為範圍從 -128 至 +127 的系統上，
int 0x80,（其值等於 +128）要轉成 char 會放不下，會產生編譯器自行定義的值。
#include <stdlib.h>
int main()
{
unsigned char a =0X80;
char b =0X80;
printf("a= %d\n",a); //128
printf("b= %d\n",b); //-128
if(a == 0X80) printf("a is true\n");
if(b == 0X80) printf("b is true\n");
system("pause");
}
/*結果 a is true!*/
unsigned char 型別定義為 範圍從 0 至256
char 型別定義為範圍從 -128 至 +127 的系統上，
int 0x80,（其值等於 +128）要轉成 char 會放不下，會產生編譯器自行定義的值。
#include <stdlib.h>
int main()
{
unsigned char a =0X80;
char b =0X80;
printf("a= %d\n",a); //128
printf("b= %d\n",b); //-128
if(a == 0X80) printf("a is true\n");
if(b == 0X80) printf("b is true\n");
system("pause");
}
/*結果 a is true!*/
2011年12月29日 星期四
C ACM 167 ,8皇后問題 (吃了6個WA,終於AC!)
[心得]: runtime 0.008
1.8皇后,只是多一個2維陣列,儲存資料!
2.輸出要向右對齊五格 printf("%5d\n",answer);
3.可以試試number全為0的狀況,答案是不是0,全為1的狀況,答案是不是8,這樣Debug很快!
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAXSIZE 8
int sum;;
int answer;
int queen[MAXSIZE+1][MAXSIZE+1];
int left_diag[2*MAXSIZE+1];
int right_diag[2*MAXSIZE+1];
int column_map[MAXSIZE+1];
void max_queen(int sum)
{
if(answer <sum)
answer=sum;
sum=0;
}
void queens(int sum,int x)
{
int j;
if(x>MAXSIZE){
max_queen(sum);
}
else{
for(j=1;j<=MAXSIZE;j++){
int R =x-j+MAXSIZE;
int L=x+j;
if(left_diag[L]&&right_diag[R]&&column_map[j]){
left_diag[L]=right_diag[R]=column_map[j]=0;
queens(sum +queen[x][j],x+1);
left_diag[L]=right_diag[R]=column_map[j]=1;
}
}
}
}
int main()
{
int i,j,data;
scanf("%d",&data);
while(data--){
for(i=1;i<=MAXSIZE;i++){
for(j=1;j<=MAXSIZE;j++){
scanf("%d",&queen[i][j]);
}
}
for(i=1;i<=2*MAXSIZE;i++)
left_diag[i] = right_diag[i]=1;
for(i=1;i<=MAXSIZE;i++)
column_map[i]=1;
answer=0;
sum=0;
queens(0,1);
printf("%5d\n",answer);
}
//return 0;
system("pause");
}
1.8皇后,只是多一個2維陣列,儲存資料!
2.輸出要向右對齊五格 printf("%5d\n",answer);
3.可以試試number全為0的狀況,答案是不是0,全為1的狀況,答案是不是8,這樣Debug很快!
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAXSIZE 8
int sum;;
int answer;
int queen[MAXSIZE+1][MAXSIZE+1];
int left_diag[2*MAXSIZE+1];
int right_diag[2*MAXSIZE+1];
int column_map[MAXSIZE+1];
void max_queen(int sum)
{
if(answer <sum)
answer=sum;
sum=0;
}
void queens(int sum,int x)
{
int j;
if(x>MAXSIZE){
max_queen(sum);
}
else{
for(j=1;j<=MAXSIZE;j++){
int R =x-j+MAXSIZE;
int L=x+j;
if(left_diag[L]&&right_diag[R]&&column_map[j]){
left_diag[L]=right_diag[R]=column_map[j]=0;
queens(sum +queen[x][j],x+1);
left_diag[L]=right_diag[R]=column_map[j]=1;
}
}
}
}
int main()
{
int i,j,data;
scanf("%d",&data);
while(data--){
for(i=1;i<=MAXSIZE;i++){
for(j=1;j<=MAXSIZE;j++){
scanf("%d",&queen[i][j]);
}
}
for(i=1;i<=2*MAXSIZE;i++)
left_diag[i] = right_diag[i]=1;
for(i=1;i<=MAXSIZE;i++)
column_map[i]=1;
answer=0;
sum=0;
queens(0,1);
printf("%5d\n",answer);
}
//return 0;
system("pause");
}
C ACM 167 (試過很多測試答案 都對了 為什麼過不了?)
心得:WA原因 沒有考慮全為0的狀況,所以WA!
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAXSIZE 8
int sum=0;;
int answer =0;
int queen[MAXSIZE+1][MAXSIZE+1];
int queen_display[MAXSIZE+1];
int left_diag[2*MAXSIZE+1];
int right_diag[2*MAXSIZE+1];
int column_map[MAXSIZE+1];
void print_queen(){
int i,j;
sum=0;
for(i=1;i<=MAXSIZE;i++){
for(j=1;j<=MAXSIZE;j++){
if(queen_display[i]==j)
sum= sum +queen[i][j];
}
}
}
void max_queen(int sum)
{
if(answer <sum)
answer=sum;
sum=0;
}
void queens(int x)
{
int j;
if(x>MAXSIZE){
print_queen();
max_queen(sum);
}
else{
for(j=1;j<=MAXSIZE;j++){
int R =x-j+MAXSIZE;
int L=x+j;
if(left_diag[L]&&right_diag[R]&&column_map[j]){
queen_display[x]=j;
left_diag[L]=right_diag[R]=column_map[j]=0;
queens(x+1);
left_diag[L]=right_diag[R]=column_map[j]=1;
}
}
}
}
int main()
{
int i,j,data;
scanf("%d",&data);
while(data--){
for(i=1;i<=MAXSIZE;i++){
for(j=1;j<=MAXSIZE;j++){
scanf("%d",&queen[i][j]);
}
}
for(i=1;i<=2*MAXSIZE;i++)
left_diag[i] = right_diag[i]=1;
for(i=1;i<=MAXSIZE;i++)
column_map[i]=1;
queens(1);
printf("%5d\n",answer);
}
//return 0;
system("pause");
}
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAXSIZE 8
int sum=0;;
int answer =0;
int queen[MAXSIZE+1][MAXSIZE+1];
int queen_display[MAXSIZE+1];
int left_diag[2*MAXSIZE+1];
int right_diag[2*MAXSIZE+1];
int column_map[MAXSIZE+1];
void print_queen(){
int i,j;
sum=0;
for(i=1;i<=MAXSIZE;i++){
for(j=1;j<=MAXSIZE;j++){
if(queen_display[i]==j)
sum= sum +queen[i][j];
}
}
}
void max_queen(int sum)
{
if(answer <sum)
answer=sum;
sum=0;
}
void queens(int x)
{
int j;
if(x>MAXSIZE){
print_queen();
max_queen(sum);
}
else{
for(j=1;j<=MAXSIZE;j++){
int R =x-j+MAXSIZE;
int L=x+j;
if(left_diag[L]&&right_diag[R]&&column_map[j]){
queen_display[x]=j;
left_diag[L]=right_diag[R]=column_map[j]=0;
queens(x+1);
left_diag[L]=right_diag[R]=column_map[j]=1;
}
}
}
}
int main()
{
int i,j,data;
scanf("%d",&data);
while(data--){
for(i=1;i<=MAXSIZE;i++){
for(j=1;j<=MAXSIZE;j++){
scanf("%d",&queen[i][j]);
}
}
for(i=1;i<=2*MAXSIZE;i++)
left_diag[i] = right_diag[i]=1;
for(i=1;i<=MAXSIZE;i++)
column_map[i]=1;
queens(1);
printf("%5d\n",answer);
}
//return 0;
system("pause");
}
2011年12月28日 星期三
C 8 Queens
心得 :
只要知道如何判斷主,從對角線有沒有放皇后的方法,
還有注意同一行有沒有其他皇后,
之後就非常簡單!
以下是網路轉載...
经观察发现，对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7)
其主对角线（即左上至右下）上的每个点的i-j+7的值（范围在(0,14)）均相等；
其从对角线（即右上至左下）上的每个点的i+j的值（范围在(0,14)）均相等；
且每个主对角线之间的i-j+7的值均不同，每个从对角线之间的i-j+7的值亦不同；
如a[3][4]:
主：3-4+7=6
从：3+4=7
因此可设两个数组b[15],c[15]分别表示主、从对角线是否安全
（为1表示有皇后，不安全；为0表示安全）
http://aikosenoo.pixnet.net/blog/post/8249576 8皇后有詳細介紹
以上方法是轉載自網路的
#include <stdio.h>
#include <stdlib.h>
char *left_diag,*right_diag;
char *column_map,*queen_map;
int n;
int answer=0;
void print_queen()
{
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
printf("%c",(*(queen_map+i)==j)?'Q':'*');
printf("\n");
}
printf("\n");
}
void queen(int x)
{
int j;
if(x>n){
if(n!=0)
answer++;
print_queen();
}
else{
for(j=1;j<=n;j++){
int R=x-j+8;
int L=x+j;
if(*(left_diag+L)&&*(right_diag+R)&&*(column_map+j)){
*(queen_map+x)=j;
*(column_map+j)=*(left_diag+L)=*(right_diag+R)=0;
queen(x+1);
*(column_map+j)=*(left_diag+L)=*(right_diag+R)=1;
}
}
}
}
int main()
{
int i;
printf("please input N :");
scanf("%d",&n);
left_diag = malloc(sizeof(int)*(n*2-1));
right_diag = malloc(sizeof(int)*(n*2-1));
column_map= malloc(sizeof(int)*(n+1));
queen_map=malloc(sizeof(int)*(n+1));
for(i=1;i<=n*2;i++)
*(left_diag+i)=*(right_diag+i)=1;
for(i=1;i<=n;i++)
*(column_map+i)=*(queen_map+i)=1;
queen(1);
free(left_diag);
free(right_diag);
free(column_map);
free(queen_map);
printf("The Queen answer of %d is %d\n",n,answer);
system("pause");
}
只要知道如何判斷主,從對角線有沒有放皇后的方法,
還有注意同一行有沒有其他皇后,
之後就非常簡單!
以下是網路轉載...
经观察发现，对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7)
其主对角线（即左上至右下）上的每个点的i-j+7的值（范围在(0,14)）均相等；
其从对角线（即右上至左下）上的每个点的i+j的值（范围在(0,14)）均相等；
且每个主对角线之间的i-j+7的值均不同，每个从对角线之间的i-j+7的值亦不同；
如a[3][4]:
主：3-4+7=6
从：3+4=7
因此可设两个数组b[15],c[15]分别表示主、从对角线是否安全
（为1表示有皇后，不安全；为0表示安全）
http://aikosenoo.pixnet.net/blog/post/8249576 8皇后有詳細介紹
以上方法是轉載自網路的
#include <stdio.h>
#include <stdlib.h>
char *left_diag,*right_diag;
char *column_map,*queen_map;
int n;
int answer=0;
void print_queen()
{
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
printf("%c",(*(queen_map+i)==j)?'Q':'*');
printf("\n");
}
printf("\n");
}
void queen(int x)
{
int j;
if(x>n){
if(n!=0)
answer++;
print_queen();
}
else{
for(j=1;j<=n;j++){
int R=x-j+8;
int L=x+j;
if(*(left_diag+L)&&*(right_diag+R)&&*(column_map+j)){
*(queen_map+x)=j;
*(column_map+j)=*(left_diag+L)=*(right_diag+R)=0;
queen(x+1);
*(column_map+j)=*(left_diag+L)=*(right_diag+R)=1;
}
}
}
}
int main()
{
int i;
printf("please input N :");
scanf("%d",&n);
left_diag = malloc(sizeof(int)*(n*2-1));
right_diag = malloc(sizeof(int)*(n*2-1));
column_map= malloc(sizeof(int)*(n+1));
queen_map=malloc(sizeof(int)*(n+1));
for(i=1;i<=n*2;i++)
*(left_diag+i)=*(right_diag+i)=1;
for(i=1;i<=n;i++)
*(column_map+i)=*(queen_map+i)=1;
queen(1);
free(left_diag);
free(right_diag);
free(column_map);
free(queen_map);
printf("The Queen answer of %d is %d\n",n,answer);
system("pause");
}
2011年12月27日 星期二
C ACM 591 Box of Bricks
[心得] 0.004
1.題目:Output a blank line after each set. 要多空一行 不然會wrong answer
2.The minimum number of moves is 5. (5後面有句點!)
#include <stdio.h>
#include <stdlib.h>
int main()
{
int block;
int arr[110];
int i;
int average,sum=0;
int move=0;
int set=1;
while(scanf("%d",&block)==1){
if(block==0) break;
move =0;
sum=0;
for(i=0;i<block;i++)
scanf("%d",&arr[i]);
for(i=0;i<block;i++)
sum=sum+arr[i];
average = sum /block;
for(i=0;i<block;i++){
if(average >arr[i])
move=move+average-arr[i];
}
printf("Set #%d\n",set);
printf("The minimum number of moves is %d.\n\n",move);
set++;
}
//return 0;
system("pause");
}
1.題目:Output a blank line after each set. 要多空一行 不然會wrong answer
2.The minimum number of moves is 5. (5後面有句點!)
#include <stdio.h>
#include <stdlib.h>
int main()
{
int block;
int arr[110];
int i;
int average,sum=0;
int move=0;
int set=1;
while(scanf("%d",&block)==1){
if(block==0) break;
move =0;
sum=0;
for(i=0;i<block;i++)
scanf("%d",&arr[i]);
for(i=0;i<block;i++)
sum=sum+arr[i];
average = sum /block;
for(i=0;i<block;i++){
if(average >arr[i])
move=move+average-arr[i];
}
printf("Set #%d\n",set);
printf("The minimum number of moves is %d.\n\n",move);
set++;
}
//return 0;
system("pause");
}
C ACM 579 Clock Hands
[心得] : 0.032
1:不可以用abs 因為 int abs(),浮點數會出不來
2.h_angle=h*30+((float)(m*6)/12); 因為 int m所以運算時記得 轉型
3.時針的角度ㄧ格為6度,時針走一小時 就跑了30度, 加上分針每跑ㄧ分,時針轉的角度是分針的1/12
4.要記得考慮 0:00 的狀況要跳出迴圈,不然會 Wrong answer!
5.大於180度時 ,要取小的角度 (所以用360度去減)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int h;
int m;
float h_angle;
float m_angle;
float angle;
while(scanf("%d:%d",&h,&m)==2)
{
if(h==0 && m==0)
break;
m_angle = m*6;
h_angle=h*30+((float)(m*6)/12);
if(h_angle > m_angle)
angle = h_angle -m_angle;
else
angle = m_angle -h_angle;
if(angle >180)
printf("%.3f\n",(360-angle));
else
printf("%.3f\n",angle);
}
system("pause");
//return 0;
}
1:不可以用abs 因為 int abs(),浮點數會出不來
2.h_angle=h*30+((float)(m*6)/12); 因為 int m所以運算時記得 轉型
3.時針的角度ㄧ格為6度,時針走一小時 就跑了30度, 加上分針每跑ㄧ分,時針轉的角度是分針的1/12
4.要記得考慮 0:00 的狀況要跳出迴圈,不然會 Wrong answer!
5.大於180度時 ,要取小的角度 (所以用360度去減)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int h;
int m;
float h_angle;
float m_angle;
float angle;
while(scanf("%d:%d",&h,&m)==2)
{
if(h==0 && m==0)
break;
m_angle = m*6;
h_angle=h*30+((float)(m*6)/12);
if(h_angle > m_angle)
angle = h_angle -m_angle;
else
angle = m_angle -h_angle;
if(angle >180)
printf("%.3f\n",(360-angle));
else
printf("%.3f\n",angle);
}
system("pause");
//return 0;
}
C acm494 kindergarten counting game
[心得] //runtime 0.004
1.ctype.h 的函數 isalpha() 測試參數是否為字母，滿足條件回傳非 0 的值，否則回傳 0 。
2.如果Array size 設定太小,就會ㄧ直 Wrong Answer!
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int main()
{
char s[1000];
int i;
int counter =0;
while(fgets(s,sizeof(s),stdin)!=NULL) // 可以換成while(gets(s)){ ....}
{
counter=0;
for(i =0;s[i]!='\0';i++){
if(isalpha(s[i])>0 && isalpha(s[i+1])==0)
counter ++;
}
printf("%d\n",counter);
}
system("pause");
//return 0;
}
1.ctype.h 的函數 isalpha() 測試參數是否為字母，滿足條件回傳非 0 的值，否則回傳 0 。
2.如果Array size 設定太小,就會ㄧ直 Wrong Answer!
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int main()
{
char s[1000];
int i;
int counter =0;
while(fgets(s,sizeof(s),stdin)!=NULL) // 可以換成while(gets(s)){ ....}
{
counter=0;
for(i =0;s[i]!='\0';i++){
if(isalpha(s[i])>0 && isalpha(s[i+1])==0)
counter ++;
}
printf("%d\n",counter);
}
system("pause");
//return 0;
}
2011年12月26日 星期一
C acm 272 TeX Quotes
心得 // runtime 0.055
只要一直讀入字元，如果是雙引號(")就判斷出現是第奇數次還是偶數次，如果是奇數次就輸出(``)；如果是偶數次，輸出('')；其他狀況則直接把字元輸出就好
#include <stdio.h></stdio.h>
#include <stdlib.h></stdlib.h>
int main()
{
char c;
int i=1;
while((c=getchar())!=EOF){
if(c =='"'){
if(i==1){
putchar('`');
putchar('`');
i=0;
}
else{
putchar('\'');
putchar('\'');
i=1;
}
}else
putchar(c);
}
return 0;
}
只要一直讀入字元，如果是雙引號(")就判斷出現是第奇數次還是偶數次，如果是奇數次就輸出(``)；如果是偶數次，輸出('')；其他狀況則直接把字元輸出就好
#include <stdio.h></stdio.h>
#include <stdlib.h></stdlib.h>
int main()
{
char c;
int i=1;
while((c=getchar())!=EOF){
if(c =='"'){
if(i==1){
putchar('`');
putchar('`');
i=0;
}
else{
putchar('\'');
putchar('\'');
i=1;
}
}else
putchar(c);
}
return 0;
}
C ACM477 Points in Figures: Rectangles and Circles
[心得] : // runtime 0.012
判斷是否在圓內,利用距離公式,求出與圓心距離,是否小於半徑,是 則該點落於圓內!
距離公式: sqrt((pow(x2-x1),2)+pow((y2-y1),2)))
記得要 #include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXSIZE 10
int main()
{
double array[MAXSIZE ][MAXSIZE ];
double a, b;
char s[MAXSIZE];
int m=0;
int i,j;
int counter =1;
int flag=0;
while(scanf("%s",&s[m])==1){
if(s[m]=='*')
break;
if(s[m] == 'r')
scanf("%lf %lf %lf %lf",&array[m][0],&array[m][1],&array[m][2],&array[m][3]);
else if(s[m] == 'c')
scanf("%lf %lf %lf",&array[m][0],&array[m][1],&array[m][2]);
m++;
}
while(scanf("%lf %lf",&a,&b)==2){
if(a==9999.9 ||b==9999.9)
break;
for(i=0;i<=m;i++){
if(s[i] == 'r'){
if(a >array[i][0]&&a<array[i][2] && b>array[i][3]&&b <array[i][1]){
flag =1;
printf("Point %d is contained in figure %d\n",counter,(i+1));
}
}
if(s[i] == 'c'){
if(array[i][2]>sqrt(pow((a-array[i][0]),2)+pow((b-array[i][1]),2))){
flag =1;
printf("Point %d is contained in figure %d\n",counter,(i+1));
}
}
}
if(flag == 0)
printf("Point %d is not contained in any figure\n",counter);
counter++;
flag = 0;
}
system("pause");
//return 0;
}
判斷是否在圓內,利用距離公式,求出與圓心距離,是否小於半徑,是 則該點落於圓內!
距離公式: sqrt((pow(x2-x1),2)+pow((y2-y1),2)))
記得要 #include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXSIZE 10
int main()
{
double array[MAXSIZE ][MAXSIZE ];
double a, b;
char s[MAXSIZE];
int m=0;
int i,j;
int counter =1;
int flag=0;
while(scanf("%s",&s[m])==1){
if(s[m]=='*')
break;
if(s[m] == 'r')
scanf("%lf %lf %lf %lf",&array[m][0],&array[m][1],&array[m][2],&array[m][3]);
else if(s[m] == 'c')
scanf("%lf %lf %lf",&array[m][0],&array[m][1],&array[m][2]);
m++;
}
while(scanf("%lf %lf",&a,&b)==2){
if(a==9999.9 ||b==9999.9)
break;
for(i=0;i<=m;i++){
if(s[i] == 'r'){
if(a >array[i][0]&&a<array[i][2] && b>array[i][3]&&b <array[i][1]){
flag =1;
printf("Point %d is contained in figure %d\n",counter,(i+1));
}
}
if(s[i] == 'c'){
if(array[i][2]>sqrt(pow((a-array[i][0]),2)+pow((b-array[i][1]),2))){
flag =1;
printf("Point %d is contained in figure %d\n",counter,(i+1));
}
}
}
if(flag == 0)
printf("Point %d is not contained in any figure\n",counter);
counter++;
flag = 0;
}
system("pause");
//return 0;
}
C ACM 476 Points in Figures: Rectangles
[心得] runtime 0.20
因為輸入資料為 浮點數 所以用 double 宣告陣列, 以%lf方式儲存
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
int main()
{
double array[MAXSIZE ][MAXSIZE ];
double a, b;
char s[MAXSIZE];
int m=0;
int i,j;
int counter =1;
int flag=0;
while(scanf("%s",&s[m])==1){
if(s[m]=='*')
break;
scanf("%lf %lf %lf %lf",&array[m][0],&array[m][1],&array[m][2],&array[m][3]);
m++;
}
while(scanf("%lf %lf",&a,&b)==2){
if(a==9999.9 ||b==9999.9)
break;
for(i=0;i<=m;i++){
if(a >array[i][0]&&a<array[i][2]&& b >array[i][3]&&b <array[i][1]){
flag =1;
printf("Point %d is contained in figure %d\n",counter,(i+1));
}
}
if(flag == 0)
printf("Point %d is not contained in any figure\n",counter);
counter++;
flag = 0;
}
system("pause");
//return 0;
}
因為輸入資料為 浮點數 所以用 double 宣告陣列, 以%lf方式儲存
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
int main()
{
double array[MAXSIZE ][MAXSIZE ];
double a, b;
char s[MAXSIZE];
int m=0;
int i,j;
int counter =1;
int flag=0;
while(scanf("%s",&s[m])==1){
if(s[m]=='*')
break;
scanf("%lf %lf %lf %lf",&array[m][0],&array[m][1],&array[m][2],&array[m][3]);
m++;
}
while(scanf("%lf %lf",&a,&b)==2){
if(a==9999.9 ||b==9999.9)
break;
for(i=0;i<=m;i++){
if(a >array[i][0]&&a<array[i][2]&& b >array[i][3]&&b <array[i][1]){
flag =1;
printf("Point %d is contained in figure %d\n",counter,(i+1));
}
}
if(flag == 0)
printf("Point %d is not contained in any figure\n",counter);
counter++;
flag = 0;
}
system("pause");
//return 0;
}
C ACM 458 The Decoder
[第一種方法]
[心得] : 少一個 printf("\n"); 判斷時,一值wrong answer
#include <stdio.h></stdio.h>
int main()
{
char c[10000];
int i;
while(fgets(c,sizeof(c),stdin)!=NULL){
for(i=0;c[i]!='\n';i++)
printf("%c",c[i]-7);
printf("\n");
}
return 0;
}
/*run time = 0.096*/
[第二種方法]
[心得]:int c;宣告為 char時,一值wrong answer
#include <stdio.h></stdio.h>
int main()
{
int c;
while((c=getchar())!=EOF){
putchar((c>31)?c-7:c);
}
return 0;
}
/*run time = 0.024*/
[心得] : 少一個 printf("\n"); 判斷時,一值wrong answer
#include <stdio.h></stdio.h>
int main()
{
char c[10000];
int i;
while(fgets(c,sizeof(c),stdin)!=NULL){
for(i=0;c[i]!='\n';i++)
printf("%c",c[i]-7);
printf("\n");
}
return 0;
}
/*run time = 0.096*/
[第二種方法]
[心得]:int c;宣告為 char時,一值wrong answer
#include <stdio.h></stdio.h>
int main()
{
int c;
while((c=getchar())!=EOF){
putchar((c>31)?c-7:c);
}
return 0;
}
/*run time = 0.024*/
C acm 10055 Hashmat the brave warrior
[心得]
1.不超過2的32次方是陷阱，要使用 long long int
2.小心 fabs 不吃 lld，要自己寫
3.a>=b (記得加=)
4.c= getchar; //c 記得宣告為 int 型態
#include <stdio.h>
#include <stdlib.h>
int main()
{
long long int a,b;
while(scanf("%lld %lld",&a,&b)!=EOF){
if(a>=b)
printf("%lld\n",a-b);
else
printf("%lld\n",b-a);
}
return 0;
}
1.不超過2的32次方是陷阱，要使用 long long int
2.小心 fabs 不吃 lld，要自己寫
3.a>=b (記得加=)
4.c= getchar; //c 記得宣告為 int 型態
#include <stdio.h>
#include <stdlib.h>
int main()
{
long long int a,b;
while(scanf("%lld %lld",&a,&b)!=EOF){
if(a>=b)
printf("%lld\n",a-b);
else
printf("%lld\n",b-a);
}
return 0;
}
2011年12月17日 星期六
C ACM 100 : The 3n + 1 problem
原文題目:http://acm.uva.es/p/v1/100.html
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i,j;
int number1;
int number2;
printf("please number 1 and number 2:");
scanf("%d %d",&number1,&number2);
i =compare(number1,number2);
printf("%d,%d,%d",number1,number2,i);
system("pause");
}
int compare(int number1,int number2)
{
int times;
int h,low,upper;
int max =0;
int number;
if(number1>number2)
{
low=number2;
upper=number1;
}
else
{
upper=number2;
low=number1;
}
for(h=low;h<=upper;h++)
{
times=1;
number=h;
while(number!=1)
{
times++;
if(number%2==1)
number = number*3+1;
else
number = number/2;
}
if(times>=max)
max=times;
}
return max;
}
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i,j;
int number1;
int number2;
printf("please number 1 and number 2:");
scanf("%d %d",&number1,&number2);
i =compare(number1,number2);
printf("%d,%d,%d",number1,number2,i);
system("pause");
}
int compare(int number1,int number2)
{
int times;
int h,low,upper;
int max =0;
int number;
if(number1>number2)
{
low=number2;
upper=number1;
}
else
{
upper=number2;
low=number1;
}
for(h=low;h<=upper;h++)
{
times=1;
number=h;
while(number!=1)
{
times++;
if(number%2==1)
number = number*3+1;
else
number = number/2;
}
if(times>=max)
max=times;
}
return max;
}
訂閱：
文章 (Atom)