Hatena::Groupcprogramming

てーげーC言語

2009-02-08

3-2

| 15:56

タブと改行を¥t, ¥nで出力

#include <stdio.h>
#define MAX_LENGTH 256

void escape(char* s, char* t); 

int main()
{
  char s[256], t[256], c;
  char* tp; 
  char* sp; 
  
  sp = s;
  tp = t;

  while ((c = getchar()) != EOF) {
    *sp++ = c;
  }   
  *sp = '\0';

  escape(s, t); 
  printf("%s\n", t);    

  return 0;
}

void escape(char* s, char* t)
{
  while(*s) {
    switch(*s) {
      case '\n':
        *t++ = '\\';
        *t++ = 'n';
        break;
      case '\t':
        *t++ = '\\';
        *t++ = 't';
        break;
      default:
        *t++ = *s; 
    }   
    s++;
  }
  *t = '\0';
}
# ./a.out                
hello   world
!
hello\tworld\n!\n

逆版

#include <stdio.h>
#define MAX_LENGTH 256

void deescape(char* s, char* t);

int main()
{
  char s[] = "hell\to world\n!";
  char t[256];
//  char c;
  char* tp; 
  char* sp; 
  
  sp = s;
  tp = t;

//  while ((c = getchar()) != EOF) {
//    *sp++ = c;
//  } 
//  *sp = '\0';

  deescape(s, t); 
  printf("%s\n", t);    

  return 0;
}

void deescape(char* s, char* t)
{
  while(*s) {
    switch(*s) {
      case '\\':
        if (*(s+1) == 'n') {
          *t++ = '\n';
          s++;
        } else if (*(s+1) == 't') {
          *t++ = '\t';
          s++;
        } else {
          *t++ = '\\';
        }
        break;
      default:
        *t++ = *s; 
    }   
    s++;
  }
  *t = '\0';
}
# ./a.out                  
hell    o world
!

3-1

| 15:48

本にある二分検索

#include <time.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <stdio.h>

#define SIZE 1000000

double getrusage_sec()
{
    struct rusage t;
    struct timeval tv; 
    getrusage(RUSAGE_SELF, &t);
    tv = t.ru_utime;
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

int binsearch(int x, int v[], int n); 

int main()
{
  int v[SIZE];
  int i;
  double t1, t2; 

  for(i=0;i<SIZE;i++)
    v[i] = i;

  t1 = getrusage_sec();
  printf("%d\n", binsearch(109, v, SIZE));
  t2 = getrusage_sec();
  printf("time = %10.70f\n", t2 - t1);

  return 0;
}

int binsearch(int x, int v[], int n)  
{
  int low, high, mid;

  low = 0;
  high = n-1;
  while (low <= high) {
    mid = (low+high) / 2;
    if (x < v[mid]) 
      high = mid -1; 
    else if (x > v[mid])
      low = mid + 1;
    else
      return mid;
  }
  return -1;
}
# ./a.out                
109
time = 0.0000280000000000002469136006766348145902156829833984375000000000000000

ループの中でチェックを1回しかしない版

#include <sys/resource.h>
#include <stdio.h>

#define SIZE 1000000

double getrusage_sec()
{
    struct rusage t;
    struct timeval tv; 
    getrusage(RUSAGE_SELF, &t);
    tv = t.ru_utime;
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

int binsearch(int x, int v[], int n); 

int main()
{
  int v[SIZE];
  int i;
  double t1, t2; 

  for(i=0;i<SIZE;i++)
    v[i] = i;

  t1 = getrusage_sec();
  printf("%d\n", binsearch(109, v, SIZE));
  t2 = getrusage_sec();
  printf("time = %10.70f\n", t2 - t1);

  return 0;
}

int binsearch(int x, int v[], int n)  
{
  int low, high, mid;

  low = 0;
  high = n - 1;

  mid = (low+high) / 2;

  while (low <= high && v[mid] != x) {
    mid = (low+high) / 2;
    if (x < v[mid]) 
      high = mid - 1;
    else
      low = mid + 1;
  }

  if (v[mid] == x)
    return mid;

  return -1;
}
# ./a.out                
109
time = 0.0000259999999999999814592754887598857749253511428833007812500000000000

実行時間にはほとんど差はないのでは・・