落書きノート

ふと自分が気になった事を書いてます

C言語で不定期練習

// 演習問題3-4

#include <stdio.h>
#include <stdlib.h>

int bin_search(const int a[], int n, int key) {
  int pl = 0;
  int pr = n - 1;
  int pc;
  int i;
  do {
    pc = (pl + pr) / 2;
    printf("%*s|", 3, "");
    for(i = 0; i < n; i++) {
      if(i == pl)
        printf(" <- ");
      else if(i == pc)
        printf("%*s+", 3, "");
      else if(i == pr)
        printf("%*s->", 2, "");
      else
        printf("%*s", 4, "");
    }
    puts("");
    printf("  %d|", pc);
    for(i = 0; i < n; i++)
      printf("%*s%d", 3, "", a[i]);
    puts("");
    printf("%*s|\n", 3, "");
    if(a[pc] == key)
      return pc;
    else if(a[pc] < key)
      pl = pc + 1;
    else
      pr = pc - 1;
  } while (pl <= pr);

  return -1;
}

int main(void) {
  int i, nx, ky, idx;
  int *x;

  puts("2分探索");
  printf("要素数 : ");
  scanf("%d", &nx);
  x = calloc(nx, sizeof(int));
  printf("昇順に入力してください。\n");
  printf("x[0] : ");
  scanf("%d", &x[0]);
  for(i = 1; i < nx; i++) {
    do {
      printf("x[%d] : ", i);
      scanf("%d", &x[i]);
    } while(x[i] < x[i - 1]);
  }
  printf("探す値 : ");
  scanf("%d", &ky);
  printf("%*s|", 3, "");
  for(i = 0; i < nx; i++)
    printf("%*s%d", 3, "", i);
  puts("");
  printf("---+");
  for(i = 0; i < nx; i++)
    printf("----");
  puts("--");
  idx = bin_search(x, nx, ky);
  if(idx == -1)
    puts("探索に失敗しました。");
  else
    printf("%dはx[%d]にあります。\n", ky, idx);
  free(x);
  return 0;
}

// 演習問題3-5

#include <stdio.h>
#include <stdlib.h>

int bin_search2(const int a[], int n, int key) {
  int pl = 0;
  int pr = n - 1;
  int pc;
  int i;
  int answer;
  do {
    pc = (pl + pr) / 2;
    if(a[pc] == key) {
      for(i = pc;;i--) {
        if(a[i] == key)
          continue;
        else {
          answer = i + 1;
          break;
        }
      }
      return answer;
    }
    else if(a[pc] < key)
      pl = pc + 1;
    else
      pr = pc - 1;
  } while (pl <= pr);

  return -1;
}

int main(void) {
  int i, nx, ky, idx;
  int *x;

  puts("2分探索");
  printf("要素数 : ");
  scanf("%d", &nx);
  x = calloc(nx, sizeof(int));
  printf("昇順に入力してください。\n");
  printf("x[0] : ");
  scanf("%d", &x[0]);
  for(i = 1; i < nx; i++) {
    do {
      printf("x[%d] : ", i);
      scanf("%d", &x[i]);
    } while(x[i] < x[i - 1]);
  }
  printf("探す値 : ");
  scanf("%d", &ky);
  idx = bin_search2(x, nx, ky);
  if(idx == -1)
    puts("探索に失敗しました。");
  else
    printf("%dはx[%d]にあります。\n", ky, idx);
  free(x);
  return 0;
}

新・明解C言語によるアルゴリズムとデータ構造

新・明解C言語によるアルゴリズムとデータ構造