bluish wolf

#include <stdio.h>
#include <string.h>
#include <windows.h>

#define TRUE        1
#define FALSE       0

#define REG         1
#define VIEW        2
#define SEARCH      3
#define SAVE        4
#define LOAD        5
#define EXIT        6

#define S_ITEM  1
#define S_NAME  2
#define S_PHONE  3
#define S_ADDRESS 4
#define S_GROUP  5
#define S_MD  6
#define S_EXIT  7

#define LIST_MAX    100

typedef struct _list
{
    char name[255];
    char phone[255];
    char address[255];
    char group[255];
    int used;
    int searched;
}LIST;

void Main_Menu(int *total);         // 메인 메뉴 출력
void Exit(void);           // 프로그램 종료
void Registration(LIST *member, int *total);    // 새 리스트 등록
int Auto_num(LIST* member);         // 자동 번지 설정
void Contents_input(char *title, char *contents);   // 내용 저장
void List_view(LIST *member, int total);     // 리스트 보기
void File_save(LIST *member, int total);     // 리스트 파일 저장
void File_load(LIST *member, int *total);     // 리스트 파일 읽기
void Search(LIST *member, int *total);      // 리스트 검색
void Search_Menu(void);          // 리스트 검색 메뉴
void Search_init(LIST *member);        // 리스트 검색 초기화
void Search_view(LIST *member);        // 리스트 검색 결과 출력
void Search_item(LIST *member);        // 리스트 항목별 검색
void Search_string(LIST *member, int s_title);    // 리스트 문자별 검색
void Search_MD_Menu(void);         // 리스트 수정/삭제 메뉴
void Search_MD(LIST *member, int *total);     // 리스트 수정/삭제
void Re_registration(LIST *member, int s_item, int title); // 리스트 수정 등록

/* MAIN START */
void main()
{
    LIST member[LIST_MAX] = {0};    // 멤버 등록 정보
    int choice = 0;                 // 메뉴 선택
    int total =0;                   // 리스트 등록 수

    while(TRUE)
    {
        Main_Menu(&total);

        printf("Choice >> ");
        scanf("%d", &choice);
        fflush(stdin);

        switch(choice)
        {
        case REG    : { Registration(member, &total);   break; }
        case VIEW   : { List_view(member, total);  break; }
        case SEARCH : { Search(member, &total);   break; }
        case SAVE   : { File_save(member, total);  break; }
        case LOAD   : { File_load(member, &total);  break; }
        case EXIT   : { Exit();       break; }
        }
  system("pause");
    }
}

/* 메인 메뉴를 출력 합니다. */
void Main_Menu(int *total)
{
    system("cls");
    puts("");
    puts("┏━━━━━━━━━━━━━━━━━━┓");
    puts("┃          MY  ADDRESS BOOK          ┃");
    puts("┣━━━━━━━━━━━━━━━━━━┫");
    puts("┃   1. REGISTRATION                  ┃");
    puts("┃   2. LIST VIEW                     ┃");
    puts("┃   3. SEARCH <MODIFY / DELETE>      ┃");
    puts("┃   4. FILE SAVE                     ┃");
    puts("┃   5. FILE LOAD                     ┃");
    puts("┃   6. EXIT                          ┃");
    puts("┣━━━━━━━━━━━━━━━━━━┫");
 printf("┃   Total of list : %3d item.        ┃\n", *total);
 puts("┗━━━━━━━━━━━━━━━━━━┛");
    puts("");
}

/* 프로그램을 종료 합니다. */
void Exit(void)
{
    puts("");
    puts("┏━━━━━━━━━━━━━━━━━━┓");
    puts("┃            PROGRAM  END            ┃");
    puts("┗━━━━━━━━━━━━━━━━━━┛");
    puts("");
    exit(TRUE);
}

/* 새로운 주소를 등록 합니다. */
void Registration(LIST *member, int *total)
{
    int num, flag, i;
    char group[5][10] = {"FAMILY", "RELATIVE", "FRIEND", "COLLEAGUE", "Ete."};
    char item[5], decision;

 do
 {
  system("cls");

  if(*total == LIST_MAX)
  {
   puts("LIST FULL, Registration failed !");
   return;
  }

  do
  {
   flag = FALSE;
   num = Auto_num(member);
   printf("Auto register : [%3d] >> ", ++num);
   gets(item);
       
   if(item[0] != '\0')
   {
    num = atoi(item);
    if(member[num-1].used != 0)
    {
     flag = TRUE;
     printf("%d of list is already registered.\n", num);
     puts("Please, try again");
     system("pause");
     system("cls");
    }
   }
  }while(flag == TRUE);
  
  printf("\nRegistration : [%3d]\n", num);
  Contents_input("NAME\t", member[num-1].name);
  Contents_input("PHONE\t", member[num-1].phone);
  Contents_input("ADDRESS\t", member[num-1].address);

  do
  {
   for(i = 0; i < 5; i++)
    printf("\t%d. %s", i+1, group[i]);
   printf("\nGROUP\t>> ");
   scanf("%d", &i);
   fflush(stdin);
  }while (i < 0 && i > 6);
   
  strcpy(member[num-1].group, group[i-1]);
   
  printf("\nDo you want save? <N/n> or other keys >> ");
  decision = getchar();
  fflush(stdin);
  puts("");

  if( strchr("Nn", decision) != NULL )
   puts("SAVE Canceled.\n");
  else
  {
   member[num-1].used = 1;
   printf("SAVE Complete. Total of list : %3d item.\n", ++*total);
  }

  printf("\nDo you want input continue? <Y/y> or other keys >> ");
  decision = getchar();
  fflush(stdin);
  puts("");
 }while(strchr("Yy", decision) != NULL);
}

/* 빈번지를 자동으로 설정 합니다. */
int Auto_num(LIST *member)
{
    int i=0;
    while(member[i].used != 0)
  i++;
    return (i);
}

/* 타이틀을 출력하고 입력된 내용을 등록 합니다. */
void Contents_input(char *title, char *contents)
{
    do
    {
        printf("%s>> ", title);
        gets(contents);
    }while(contents[0] == '\0');
}

/* 등록된 리스트를 출력 합니다. */
void List_view(LIST *member, int total)
{
 int i;
 system("cls");

 if(total == 0)
 {
  puts("List is empty.");
  return;
 }

 puts("No.\t NAME\t PHONE\t ADDRESS\t GROUP\t");
 for(i = 0; i < LIST_MAX ; i++)
 {
  if(member[i].used != 0)
  {
   printf("[%3d]\t %s\t %s\t %s\t %s\t\n",
    i+1, member[i].name, member[i].phone, member[i].address, member[i].group);
  }
 }
}

/* 리스트를 파일로 저장 합니다. */
void File_save(LIST *member, int total)
{
 FILE *fp;
 int i;

 if(total == 0)
 {
  puts("List is empty.");
  puts("SAVE Canceled.\n");
  return;
 }
 
 fp = fopen("my_list.txt", "w");
 if(fp == NULL)
 {
  puts("Don't have enough of storage capacity.");
  puts("SAVE Canceled.\n");
  return;
 }

 for(i = 0; i < LIST_MAX ; i++)
 {
  if(member[i].used == 1)
  {
   fprintf(fp, "%d>%s>%s>%s>%s\n",
    i, member[i].name, member[i].phone, member[i].address, member[i].group);
   printf("[%3d]\t %s\t %s\t %s\t %s\t\n",
    i+1, member[i].name, member[i].phone, member[i].address, member[i].group);
  }
 }
 puts("SAVE Complete !!!\n");
 fclose(fp);
}

/* 리스트 파일을 읽어 옵니다. */
void File_load(LIST *member, int *total)
{
 FILE *fp;
 char decision, ch;
 int i, num;

 fp = fopen("my_list.txt", "r");

 if(fp == NULL)
 {
  puts("Can't read [my_list.txt] file.");
  puts("LOAD Canceled.\n");
  return;
 }

 if(*total != 0)
 {
  printf("\nDo you want file load? Your current data will be lost !\n");
  printf("<Y/y> or other keys >> ");
  decision = getchar();
  fflush(stdin);
  puts("");

  if( strchr("Yy", decision) != NULL )
  {
   *total = 0;
   for(i = 0; i < LIST_MAX; i++)
    member[i].used = 0;
   puts("Memory Initialized.\n");
  }
  else
  {
   puts("LOAD Canceled.\n");
   fclose(fp);
  }
 }

 puts("Data Loading...\n");
 while( (ch = fgetc(fp)) != EOF )
 {
  num = 0;
  do
  {
   num = num * 10 + (ch -'0');
  }while((ch = fgetc(fp)) != '>');

  i = 0;
  while((ch = fgetc(fp)) != '>')
   member[num].name[i++] = ch;
  member[num].name[i] = '\0';

  i = 0;
  while((ch = fgetc(fp)) != '>')
   member[num].phone[i++] = ch;
  member[num].phone[i] = '\0';

  i = 0;
  while((ch = fgetc(fp)) != '>')
   member[num].address[i++] = ch;
  member[num].address[i] = '\0';

  i = 0;
  while((ch = fgetc(fp)) != '\n')
   member[num].group[i++] = ch;
  member[num].group[i] = '\0';

  member[num].used = 1;

  ++*total;

  printf("[%3d]\t %s\t %s\t %s\t %s\t\n",
   num+1, member[num].name, member[num].phone, member[num].address, member[num].group);
  Sleep(300);
 }
 puts("\nLOAD Complete !!!\n");
 fclose(fp);
}

/* 검색 메뉴를 출력 합니다. */
void Search_Menu(void)
{
    system("cls");
    puts("");
    puts("┏━━━━━━━━━━━━━━━━━━┓");
    puts("┃            SEARCH MENU             ┃");
    puts("┣━━━━━━━━━━━━━━━━━━┫");
    puts("┃   1. Item Number Search            ┃");
    puts("┃   2. Name Search                   ┃");
    puts("┃   3. Phone Number Search           ┃");
    puts("┃   4. Address Search                ┃");
    puts("┃   5. Group Search                  ┃");
    puts("┃   6. Modify / Delete               ┃");
    puts("┃   7. EXIT                          ┃");
 puts("┗━━━━━━━━━━━━━━━━━━┛");
    puts("");
}

/* 수정/검색 메뉴를 출력 합니다. */
void Search_MD_Menu(void)
{
 puts("");
    puts("┏━━━━━━━━━━━━━━━━━━┓");
    puts("┃   1. Modify                        ┃");
    puts("┃   2. Delete                        ┃");
    puts("┃   3. EXIT                          ┃");
 puts("┗━━━━━━━━━━━━━━━━━━┛");
    puts("");
}

/* 리스트를 항목별로 검색 합니다. */
void Search(LIST *member, int *total)
{
 int choice, cnt = 0;

 while(TRUE)
 {
  Search_Menu();

  if(*total == 0)
  {
   puts("List is empty.");
   puts("SEARCH Canceled.\n");
   return;
  }
  printf("Choice >> ");
        scanf("%d", &choice);
        fflush(stdin);

        switch(choice)
        {
        case S_ITEM  : { Search_item(member);    break; }
        case S_NAME  : { Search_string(member, S_NAME);  break; }
        case S_PHONE : { Search_string(member, S_PHONE);  break; }
        case S_ADDRESS : { Search_string(member, S_ADDRESS); break; }
        case S_GROUP : { Search_string(member, S_GROUP);  break; }
        case S_MD  : { Search_MD(member, total);     break; }
  case S_EXIT  : { return; }
        }
 }
}

/* 검색 조건을 초기화 합니다. */
void Search_init(LIST *member)
{
 int i;
 for(i = 0; i < LIST_MAX; i++)
  member[i].searched = 0;
}

/* 검색된 결과를 출력 합니다. */
void Search_view(LIST *member)
{
 int i;

 puts("No.\t NAME\t PHONE\t ADDRESS\t GROUP\t");
 for(i = 0; i < LIST_MAX ; i++)
 {
  if(member[i].searched == 1)
  {
   printf("[%3d]\t %s\t %s\t %s\t %s\t\n",
    i+1, member[i].name, member[i].phone, member[i].address, member[i].group);
  }
 }
}

/* 항목 번호로 검색을 수행 합니다. */
void Search_item(LIST *member)
{
 int num;
 char decision;

 do
 {
  Search_init(member);
  printf("Item Number >> ");
  scanf("%d", &num);
  fflush(stdin);

  if(member[num-1].used == 0)
  {
   printf("[%3d] Item is Empty !!!\n", num);
   printf("Do you want item search continue? (Y/y) >> ");
   decision = getchar();
   fflush(stdin);
  }
  else
  {
   member[num-1].searched = 1;
   Search_view(member);
   printf("Do you want item search continue? (Y/y) >> ");
   decision = getchar();
   fflush(stdin);
  }
 }while(strchr("Yy", decision) != NULL);
}

/* 타이틀별로 검색을 수행 합니다. */
void Search_string(LIST *member, int s_title)
{
 char s_buf[255], decision;
 int i, cnt;

 do
 {
  cnt = 0;

  Search_init(member);
  printf("Search >> ");
  scanf("%s", &s_buf);
  fflush(stdin);

  for(i = 0; i < LIST_MAX; i++)
  {
   if(member[i].used != 0)
   {
    switch(s_title)
    {
    case S_NAME :
     {
      if(strstr(member[i].name, s_buf) != NULL)
      {
       member[i].searched = 1;
       cnt++;
      }
     }
    case S_PHONE :
     {
      if(strstr(member[i].phone, s_buf) != NULL)
      {
       member[i].searched = 1;
       cnt++;
      }
     }
    case S_ADDRESS :
     {
      if(strstr(member[i].address, s_buf) != NULL)
      {
       member[i].searched = 1;
       cnt++;
      }
     }
    case S_GROUP :
     {
      if(strstr(member[i].group, s_buf) != NULL)
      {
       member[i].searched = 1;
       cnt++;
      }
     }
    }
   }
  }

  if(cnt == 0)
  {
   printf("[%s] is not match !!!", s_buf);
   printf("Do you want search continue? (Y/y) >> ");
   decision = getchar();
   fflush(stdin);
  }
  else
  {
   Search_view(member);
   printf("Do you want search continue? (Y/y) >> ");
   decision = getchar();
   fflush(stdin);
  }
 }while(strchr("Yy", decision) != NULL);
}

/* 검색된 목록에서 리스트를 수정/삭제 합니다. */
void Search_MD(LIST *member, int *total)
{
 int i, flag=0;
 char decision, mode, choice, title;

 for(i = 0; i < LIST_MAX ; i++)
 {
  if(member[i].searched == TRUE)
  {
   flag = TRUE;
  }
 }
 
 if(flag == FALSE)
 {
  puts("Search result don't exist");
  system("pause");
  return;
 }

 else
 {
  do
  {
   flag = FALSE;
   Search_MD_Menu();
   printf("Choice >> ");
   mode = getchar();
   fflush(stdin);
   Search_view(member);

   if(mode == '1')
   {
    do
    {
     printf("Motify item choice >> ");
     choice = getchar();
     fflush(stdin);

     if(member[choice-'0'-1].searched == FALSE)
     {
      puts("This item is not searched.");
     }
    }while(member[choice-'0'-1].searched != TRUE);
    
    printf("\n\t\t1.NAME 2.PHONE 3.ADDRESS 4.GROUP\n");
    printf("Motify title choice >> ");
    title = getchar();
    fflush(stdin);
    
    Re_registration(member, choice - '0', title-'0'+1);
    printf("\nDo you want Motify item continue? (Y/y) or other keys >> ");
    decision = getchar();
    fflush(stdin);
   }
   else if(mode == '2')
   {
    do
    {
     printf("\nDelete item choice >> ");
     choice = getchar();
     fflush(stdin);

     if(member[choice-'0'-1].searched == FALSE)
     {
      puts("This item is not searched.");
     }
    }while(member[choice-'0'-1].searched != TRUE);

    printf("\nDo you want Delete? (Y/y) or other keys >> ");
    decision = getchar();
    fflush(stdin);

    if(strchr("Yy", decision) != NULL)
    {
     member[(choice-1) - '0'].used = 0;
     printf("\nDELETE Complete. <Total of list : %3d item.>\n", --*total);
    }
    else
    {
     puts("DELETE Canceled");
    }
    printf("\nDo you want Delete item continue? (Y/y) or other keys >> ");
    decision = getchar();
    fflush(stdin);
   }
   else return;
  }while(strchr("Yy", decision) != NULL);
 }
}

/* 리스트를 수정 등록 합니다. */
void Re_registration(LIST *member, int s_item, int title)
{
    int i;
    char group[5][10] = {"FAMILY", "RELATIVE", "FRIEND", "COLLEAGUE", "Ete."};
    char decision;

 printf("\nRegistration : [%3d]\n", s_item);
 switch(title)
 {
 case S_NAME  : {Contents_input("NAME\t", member[s_item-1].name);  break;}
 case S_PHONE : {Contents_input("PHONE\t", member[s_item-1].phone);  break;}
 case S_ADDRESS : {Contents_input("ADDRESS\t", member[s_item-1].address); break;}
 case S_GROUP : 
  {
   Contents_input("GROUP\t", member[s_item-1].group);
   do
   {
    for(i = 0; i < 5; i++)
     printf("\t%d. %s", i+1, group[i]);
    printf("\nGROUP\t>> ");
    scanf("%d", &i);
    fflush(stdin);
   }while (i < 0 && i > 6);
   
   strcpy(member[s_item-1].group, group[i-1]);
   break;
  }
 }
   
 printf("\nDo you want save? <N/n> or other keys >> ");
 decision = getchar();
 fflush(stdin);
 puts("");
 
 if( strchr("Nn", decision) != NULL )
  puts("MODIFY Canceled.\n");
 else
 {
  member[s_item-1].used = 1;
  puts("MODIFY Complete.\n");
 }
}

에디트 플러스에서 JAVA를 사용하기 위한 설정을 해 보자.

1. 에디트 플러스 실행

  도구 -> 사용자 도구 구성 -> 추가 ->

2. 에디트 플러스 컴파일 단순 설정하기

  - 저 같은 경우는 메뉴제목은 javac (컴파일할때 쓰이는 실행파일)로 했습니다.

    메뉴 제목이므로제목은 마음대로 써도 좋습니다.

  - 명령은 옆에 ... 을 클릭 javac파일이 있는곳을 찾아가서 클릭

  - 보통 C:\Program Files\Java\jdk1.5.0_07\bin <- 이 폴더에 있죠!

  - 인수 = $(FileName)

  - 디렉토리 = $(FileDir)

  - 밑에 출력내용캡쳐 체크.

 

3. 에디트 풀러스 실행 단순 설정하기

  - 저 같은 경우는 메뉴제목은 java (컴파일된 java파일을 실행하는파일)

    메뉴제목이므로 제목은 마음대로 써도 좋습니다.

  - 명령은 옆에 ... 을 클릭 java파일이 있는곳을 찾아가서 클릭

  - 보통 C:\Program Files\Java\jdk1.5.0_07\bin <- 이것도 같은 폴더!

  - 인수 = $(FileNameNoExt)

  - 디렉토리 = $(FileDir)

설정 끝입니다.

 

실행하는 단축키는 Ctrl+순서대로입니다.

사용자도구 구성의 도구이름 순서대로니깐 맨 위에 있는것이 1입니다.

즉, 위와 같이 설정시 컴파일이 Ctrl+1, 실행이 Ctrl+2 입니다.

Let's talk about the now and future of Query by Humming(QbH). I don't want to talk about the past because there was nothing in the past. Now computer scientists are researching QbH, and I think it will be a dream technology in the future.


How far we've gone so far? Let me give real examples. In 2004, KTF(the one of Korean mobile companies) started "Search Music" service, and Verizon(the one of US mobile companies) also started "SongID" service.

http://www.muncle.com/media/mobile_news_view.jsp?seq=1396
“노래 들을 준비됐니?”라는 카피와 함께 가수 서태지의 미발표 신곡이 흐르면서 광고는 시작합니다. 시청자가 ‘휴대전화를 꺼내고’ ‘1515+통화버튼을 누른다’ ‘휴대전화를 TV에 가까이 댄다’ 등 광고 중간중간 나오는 지시를 따르면 신기하게도 휴대전화에 곡명이 뜨고, 노래를 다운받을 수 있습니다. (음악을 6초 이상 들려줘야 검색이 가능)
...KTF has promoted with Seo Taiji, who has the most powerful fandom. He released a new song through this service, but even his fans haven't used this service.

http://www.fiercemobilecontent.com/story/verizon-launches-song-identification-service/2007-05-20
Verizon Wireless announced V Cast Song ID, a new service enabling subscribers to identify a piece of music by capturing a 10-second sample via mobile handset and seconds later receiving title and artist information as well as corresponding download, ringtone and ringback offers.
...This is almost the same of KTF "Search Music". Have you ever heard this service? Maybe not.

And Bugs Music also released "Humming Search" service in October 2007, but it has closed in March 2008.


Why these services were unpopular? Why were they unsuccessful? As I used them, their performance were poor. They possibly find my songs, but not so great.

What are the problems?


1. Singers may sing incorrectly
2. There may be noise when singing
3. The program may abstract the voice to the note incorrectly
4. The program may search incorrectly
5. The Music DB may be too small or incorrect

Among these possible problems, we want to focus on searching way. we don't care noise and the abstraction from the wave sound to the note because they have already researched enough.

I think the abstraction of data to meta data is similar to MPEG-7. Actually, QbH is already included to MPEG-7 standard, it's just a provision though.

http://en.wikipedia.org/wiki/Query_by_humming

What is MPEG-7? It makes machine read audio and video. For example, we can read the jpg file and know it's Beckham, but computers can't. So we add meta-data indicates this part of the jpg file is Beckham.



MPEG-7 is similar to the Semantic Web, abstracting meta-data from data. They try to abstract semantic meanings like "It's Beckham!" from the binary data, but I'm afraid whether it's possible.


Back to QbH, we can divide vocal abstraction in two parts, the soft part and the hard part. We can abstract the wave data to the note data easily, but it's still hard to abstract the note to the semantic data like "It's Beckham!".


I'll talk how they are soft and hard in the next article.

 -프롬프트 -> minicom (엔터)-

 1. setip, sethost, setmac, setenv, netopen 수행

 2. 1.번을 수행했다면 바로 netopen

 3. tftp zImage 0x31000000 (엔터)

 4. tftp ramdisk4.gz 0x30600000 (엔터)

 5. run 0x31000000 (엔터)

 6. ID : root // PW : yan2041

 7. ifconfig eh0 10.40.1.107 netmask 255.255.255.0 (엔터)
   (위에서 10.40.1.107은 네트워크에 연결된 자신의 보드 IP)

 8. route add default gw 10.40.1.254 (엔터)

 9. route (엔터) - 라우터를 확인

10. cd /mnt/nfs (엔터)

11. ls (엔터)
    (현재 폴더에 gendisk.ko와 gpio.ko가 있는지 확인!)
    (없거나, 허가 거부가 뜬다면, 직접 /home/계정ID/driver로 이동 후, 
     각 gendisk와 gpio폴더에서 cp  gpio.ko /nfs (엔터) 와 cp gendisk.ko /nfs (엔터)를 쳐서 이동 시킴)

12. insmod gpio.ko (엔터)

13. insmod gendisk.ko (엔터)

14. lsmod (엔터)

15. mkfs.ext2 /dev/gen (엔터)

16. mount /dev/gen /mnt/hda (엔터)

17. mount (엔터) - 제대로 되었는지 확인 함.

-------------------------------------------------------------------------------
금요일은 우선 여기 까지 확인!

(문제) R명의 사람이 있다. 사람들 사이에는 서로 친구이거나 서로 적인 관계가 성립하고 있다. 그렇다면 만약 R명의 사람이 존재하기만 한다면 이중에서 3명은 서로 친구이거나 3명이 서로 적인 경우가 반드시 존재한다고 한다. 이 경우 R의 최소 값은 얼마이겠는가?

위와 같은 문제가 주어졌다. 위 문제는 Ramsey Number를 제기하는 가장 기초적인 문제로써 비둘기 집의 원리로써 쉽게 해결 할 수 있다. 한편 여기서 3명이 서로 친구(mutual friends)란 말은 (대칭적으로 서로 적이란 말에도 성립한다.) 이 3명중에서 아무나 두 명을 선택했을 때 그 두 사람은 반드시 친구인 경우인 경우를 말한다.

(풀이)

사람이 총 n명이 있다고 가정하자. 그리고 각 사람들을 점(point)으로 두고 그 사람사이의 관계를 선(edge)으로 연결하자. 이 n 개의 점을 모두 다 이은 모양의 그래프(Graph)를 Complete graph of order n (K_n)이라고 한다. 이제 이 그래프의 선분들은 2가지색으로 Coloring을 할 수 있고, 그 색들은 각각, 친구, 적이라는 의미를 가진다고 생각하면 위 문제는 변의 색이 모두 같은 삼각형을 찾는 문제로 변형이 된다.

먼저 R>5 임을 보이자. 이것은 반례를 보이면 쉽게 증명된다.

① R=5 ; Counter Example.

② R=6 : 한 사람(A)에 대해서 생각하자. Pigeonhall Principle 에 의해서 나머지 다섯 사람 중에는 적어도 세 사람 이상이 A와 친구이거나 적이고, 대칭적으로 세 사람이 친구라고 한다면 이 사람들끼리 친구 사이가 존재하면 그 두 사람과 A는 서로 친구 사이. 만일 이 세 사람이 모두 적이라면 서로 적인 경우가 되므로 적어도 R이 6이상 이라면 반드시 세 명이 서로 친구이거나 서로 적인 경우가 존재한다. 따라서 R의 최소 값은 6이다. □

(Definition) R명의 사람이 있을 때 m명이 서로 친구이거나 (mutual friends), n명이 서로 적인 경우(mutual enemies)인 경우가 반드시 생긴다고 할 때, R의 최소값을 Ramsey Number R(m,n) 이라고 정의한다.

일반적으로 Ramsey Number 의 구체적인 값에 대해서는 알려져 있지 않다. 대신에 몇몇 특수한 값들에 대해서는 이미 밝혀지고 증명이 되어 있다. 필자는 이번 원고에서 R(4,4)=18 임을 증명하려 한다.

Lemma 1) R(3,3) = 6

위에 증명되어 있다.

Lemma 2) R(4,3) = 9

(풀이)

먼저 R(4,3) > 8 임을 보이자. 이것은 R=8 일 때 4명이 서로 친구이거나 3명이 서로 적일 경우가 꼭 생기지 않는 반례를 보이면 증명이 된다. 왜냐하면 R=8 일 때 반례가 존재하면 R<8 일 때 역시 R=8 일 때의 예에서 사람을 한 명씩만 줄이면 그것이 각각의 반례가 되기 때문이다. 친구를 실선, 적을 점선으로 연결한다고 하면 R=8 일 때 다음과 같은 반례가 존재한다.

이제 R(4,3)<= 9 임을 보이자.

어떤 한 사람 A를 기준으로 친구가 6명 있다고 가정하자. 그러면 Lemma 1에 의해 이 6명 중에는 반드시 서로 친구인 세 사람이 있거나 적인 세 사람이 존재한다. 서로 적인 세 사람이 존재한다면 R(4,3)의 정의에 만족하고, 서로 친구인 세 사람이 존재한다면 A와 함께 서로 친구인 네 사람이 존재하는 것이 된다. 따라서 증명 끝.

또한 A와 적관계인 4 사람이 존재한다고 가정하자. 그러면 이 사람들 중에 서로 적인 두 사람이 있다면 A와 함께 서로 적인 세 사람이 존재하는 것이다. 그런 관계가 없다면 정의에 의해 이 네 사람은 서로 친구가 되는 것이다. 따라서 9명의 사람이 있을 때, 어떤 한 사람도 친구가 6명 이상이거나 적이 4명 이상이면 반드시 네 명이 서로 친구이거나 세 명이 서로 적인 경우가 반드시 생기게 된다.

9가 R(4,3)을 만족하지 않을 반례가 존재하기 위해선 9명의 사람 모두가 5명의 친구, 3명의 적을 가지고 있어야 한다. 즉, 위와 같은 그래프에서 각 점에 실선이 모두 5개여야 한다는 말이다. 점과 실선(edge)만으로 이루어진 Simple Graph 를 생각하면,

2e = Σdeg(v) (e는 edge 의 개수, deg(v) 는 각 꼭지점에 연결된 edge의 개수)

가 성립하는 데, deg(v)=5 이고 |v|=9 이므로, 2e = Σdeg(v) = 9×5 = 45 이다.

하지만 45는 홀수 이므로 모순. 따라서 그러한 예는 존재하지 않는다. 따라서 반드시 누군가 한 명은 6명 이상의 친구를 가지고 있거나 4명 이상의 적을 가지고 있어야 한다. 따라서 9명의 사람이 있으면 반드시 네 명이 서로 친구이거나 세 명이 서로 적인 경우를 찾을 수 있고 R(4,3)>8 에서, R(4,3)=9 이다.□

Lemma 3)

R(m,n) = R(n,m)

Lemma 4)

R(n,2) = n = R(2,n)

(증명) Lemma 3와 Lemma 4는 자명하다.

Theorem) Ramsey's Theorem.

Claim. R(m,n) ≤ R(m-1,n) + R(m,n-1) for m, n(>2) ∈ N

pf) n명의 사람이 있다고 하자. 그 중에서 임의의 고정된 한 사람 A를 잡고 각 사람들 사이의 관계를 선으로 표시하자. 즉, 친구일 때는 붉은 색을, 적일 때는 푸른색의 선분을 칠한다고 생각하자. 만일 붉은 색이 선분이 R(m-1,n) 개 이상 있다고 하면 그 사람들이랑 A 와 함께 존재해서 R(m,n) 이 만들어진다. 비슷하게 푸른색이 R(m,n-1) 개 이상 있다고 하면 역시나 A와 함께 R(m,n) 이 만들어진다. 따라서 어떤 고정된 사람 A에 대하여 총 (R(m-1,n)-1)+(R(m,n-1)-1)+1 개의 관계를 가진 사람들이 존재하면 그 Pigeonhall Principle에 의해서 R(m-1,n) 개의 붉은 색 선분이나 R(m,n-1) 개의 푸른색 선분을 가진 사람들이 존재하고 따라서 이 수는 R(m,n) 보다 크다고 할 수 있다. . □

이제 R(4,4) 가 18임을 증명하자.

Ramsey Theorem 에 의해 R(4,4) ≤ R(4,3) + R(3,4) 이 성립하고 Lemma 2와 Lemma 3에 의해 R(4,4) ≤ R(4,3)+R(3,4) = 2R(4,3) = 18 이 성립한다. R(4,3)>17 임을 보이기 위해선 R=17 일 때, 반례가 있음을 보이면 된다. 이것은 그다지 어렵지 않기 때문에 숙제로 남긴다. 여러분들이 한번 찾아보길 바란다.

이상 우리는 간단하게나마 Ramsey Number 에 대해서 알고 몇 가지 경우에 대해서 Ramsey Number 를 직접 찾고 증명해 보았다. 또한 우리는 R(4,4)=18 임을 증명할 수 있었다. 마지막으로 현재까지 밝혀진 Ramsey Number 에 대한 표는 다음과 같다.

l k	3	4	5	6	7	8
3	6	9	14	18	23	27/30
4		18	25/28	34/44
5			42/55	51/94
6				69/102

References

1. 「Ramsey Theory」, Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer (1980 ; John Wiley & Sons, Inc)

2. 「Discrete Mathematics and Its Applications」, Kenneth H. Rosen  (4th ed ; VAGA, New York)

출처 : http://math.kaist.ac.kr/%7Edeneb/study/Ramsey_Numbers.htm

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
#include<conio.h>

typedef struct _node
{
    char* data;
    struct _node* next;
    struct _node* back;
}node;
node *head, *tail;
int total, now;  // 전체페이지, 현재페이지 출력 변수

void init_line(void);
void load_file(void);
void show_header(void);
void show_page(node*);
void key_proc(void);
void move_line(int, node**);
void gotoxy(int, int);

void main()
{
    init_line();
    load_file();
    key_proc();
    puts("Program ends...");
}

//노드 초기화 함수
void init_line(void)
{
    head = (node*)malloc(sizeof(node));
    tail = (node*)malloc(sizeof(node));
    head->next = tail;
    head->back = head;
    tail->back = head;
    tail->next = tail;
}

//파일 로드 함수
void load_file(void)
{
    FILE *fp;
    char buf[256];
    node* temp;
    if((fp = fopen("test.txt","rt"))==NULL)
    {
        puts("Error : Can`t read that file.");
        exit(1);
    }
    while(!feof(fp))
    {
        fgets(buf, 255, fp);
        if(strlen(buf)>80)
            buf[80] = 0;  // 최대길이 80
        if((temp = (node*)malloc(sizeof(node))) == NULL)
        {
            puts("Error : Out of Memory.");
            exit(1);
        }
        if((temp->data = (char*)malloc(strlen(buf))) == NULL)
        {
            puts("Error : Out of Memory.");
            exit(1);
        }
        strcpy(temp->data, buf);
        temp->next = tail;
        temp->back = tail->back;
        tail->back->next = temp;
        tail->back = temp;
        total++;  //전체 갯수 증가
    }
    fclose(fp);
}  

//화면 출력 함수
void show_page(node* temp)
{
    int line = 0;
    system("cls");
    show_header();
    gotoxy(1, 2);
    while(line++ < 23 && temp != tail)
    {
        cprintf("%-80s\r", temp->data);
        temp = temp->next;
    }
}

//키 제어 함수
void key_proc(void)
{
    node* temp;
    now = 1;
    temp = head->next;
    show_page(temp);
    while(1)
    {
        //ESC키 눌렀을때
        if(GetAsyncKeyState(VK_ESCAPE) & 0x8000)
            break;
        //PgUp키 눌렀을때
        if(GetAsyncKeyState(VK_PRIOR) & 0x8000)
        {
            move_line(-23, &temp);
            show_page(temp);
        }
        //PgDn키 눌렀을때
        if(GetAsyncKeyState(VK_NEXT) & 0x8000)
        {
            move_line(23, &temp);
            show_page(temp);
        }
        //▲키 눌렀을때
        if(GetAsyncKeyState(VK_UP) & 0x8000)
        {
            move_line(-1, &temp);
            show_page(temp);
        }
        //▼키 눌렀을때
        if(GetAsyncKeyState(VK_DOWN) & 0x8000)
        {
            move_line(1, &temp);
            show_page(temp);
        }
    }
    system("cls");
}

//페이지 이동 함수
void move_line(int d, node** temp)
{
    if(d<0)
    {
        while(d++ < 0 && (*temp)->back != head)
        {
            *temp = (*temp)->back;
            now--;
        }
    }
    else
    {
        while(d-- > 0 && (*temp)->next != tail)
        {
            *temp = (*temp)->next;
            now++;
        }
    }
}

//출력화면의 최상단 화면
void show_header(void)
{
    HANDLE hout = GetStdHandle(STD_OUTPUT_HANDLE);
    CONSOLE_SCREEN_BUFFER_INFO csbi;
    GetConsoleScreenBufferInfo(hout, &csbi);

    //출력색 변환
    SetConsoleTextAttribute(hout, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    gotoxy(1, 1);
    cprintf("TVIEW : %-12s     Loc : %6d of %6d     By Jeong Jin Hwa     ", "test.txt", now, total);
    //원래색으로 변환
    SetConsoleTextAttribute(hout, csbi.wAttributes);
}

//gotoxy함수
void gotoxy(int x, int y)
{
   COORD Pos = {x - 1, y - 1};
   SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Pos);
}

//Double Linked List
#include<stdio.h>
#include<stdlib.h>

 typedef struct _node
{
     int data;
     struct _node* back;
     struct _node* next;
}node;
node *head, *tail;

 void print_all(void);
void init_link(void);
void insert_link(int x);
node* find_node(int x);
void insert_before(int x, node* y);
void del_node(node* x);
void all_del_node(void);

 void main()
{
    init_link();
    insert_link(10);
    insert_link(5);
    insert_link(8);
    insert_link(3);
    insert_link(1);
    insert_link(7);
    insert_link(8);

    printf("Inital Linked list is ");
    print_all();

     printf("Finding 4 is %s\n", find_node(4) != tail ? "successful" : "unsuccessful");
    printf("Finding 5 is %s\n", find_node(5) != tail  ? "successful" : "unsuccessful");

     puts("Inserting 7 before 5");
    insert_before(7, find_node(5));
    print_all();

     puts("Deleting 3");
    del_node(find_node(3));
    print_all();

     puts("Inserting node 2 before 10");
    insert_before(2, find_node(10));
    print_all();

     puts("Deleting 2");
    del_node(find_node(2));
    print_all();

     puts("Deleting 1");
    del_node(find_node(1));
    print_all();

     puts("Insering node 15");
    insert_before(15, head->next);
    print_all();

     puts("Deleting all node");
    all_del_node();
    print_all();
}

 //전체 노드 삭제

void all_del_node(void)
{
    node* temp;
    temp = head->next;
    while(temp != tail)
    {
        temp = temp->next;
        free(temp->back);
    }

    //노드 초기화
    head->next = tail;
    tail->back = head;
}

 

//노드를 입력받아 삭제

void del_node(node* x)
{
    if(x != tail)
    {
        x->back->next = x->next;
        x->next->back = x->back;
        free(x);
    }
    else
        puts("!!!!!!!!!!!!!!!!! Not Node !!!!!!!!!!!!!!!!!");
}

 

//찾은 노드 이전에 삽입

void insert_before(int x, node* y)
{
    node* temp = (node*)malloc(sizeof(node));

    temp->data = x;
    y->back->next = temp;
    temp->back = y->back;
    y->back = temp;
    temp->next = y;
}

 

//노드 찾기
node* find_node(int x)
{
    node* temp;
    temp = head->next;
    while(temp->data != x && temp != tail)
        temp = temp->next;
    return temp;
}

 

//노드값 화면에 출력

void print_all(void)
{
    node* temp;
    temp = head->next;
    while(temp != tail)
    {
        printf("%5d",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

 

//노드 초기화

void init_link(void)
{
    head = (node*)malloc(sizeof(node));
    tail = (node*)malloc(sizeof(node));
    head->next = tail;
    head->back = head;
    tail->next = tail;
    tail->back = head;
}

 

//노드 입력 받기
void insert_link(int x)
{
    node *a;
    node* temp = (node*)malloc(sizeof(node));
   
    a = head->next;
    while(a->data <= x && a != tail)
     a = a->next;

    temp->data = x;
    a->back->next = temp;
    temp->back = a->back;
    temp->next = a;
    a->back = temp;
}