四則

3,3,8,8 (用いる順序は自由)と四則演算を用いて 24 を作れ。

http://d.hatena.ne.jp/qqqlxl/20061108/p3
これを解くのは C言語では難しいよね、といわれたのであえて頑張る。もっと高級な言語を用いてざくっとやるのは任せた。

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

typedef struct rat
{
  int n,d;
} rat;

int gcd(int a,int b)
{
  int i = a%b;
  if(i)
      return gcd(b,i);
  else
      return b;
}

void reg(rat * a)
{
  if(a->d < 0)
    {
      a->n *= -1;
      a->d *= -1;
    }
  if(a->d)
    {
      int g = gcd(a->n,a->d);
      a->d/=g;
      a->n/=g;
    }
  else
    {
      a->n = 0;
    }
}

rat* add(rat *a, rat *b, rat*r)
{
  int d = a->d * b->d;
  int n = a->d * b->n +  b->d * a->n;
  r->d = d;
  r->n = n;
  reg(r);
  return r;
}

rat* sub(rat *a, rat *b, rat*r)
{
  rat c = *b;
  c.n *= -1;
  return add(a,&c,r);
}

rat* mul(rat *a, rat *b, rat*r)
{
  int d = a->d * b->d;
  int n = a->n * b->n;
  r->d = d;
  r->n = n;
  reg(r);
  return r;
}

rat* div(rat *a, rat *b, rat*r)
{
  rat c;
  c.n = b->d;
  c.d = b->n;
  return mul(a,&c,r);
}


typedef struct ITEM
{
  enum {NUM, FUNC} type;
  union
  {
    rat r;
    rat* (*f)(rat*,rat*,rat*);
  } val;
} item;

void mkitem(char * str, int n, item * head, item * buf)
{
      buf->type=FUNC;
      buf->val.f=NULL;
      return;
}

rat * pushrat(rat * stack, rat *val)
{
      *stack = *val;
      return ++stack;
}

rat * pushfunc(rat * stack, rat* (*f)(rat*,rat*,rat*))
{
  f(stack-2,stack-1,stack-2);
  return stack-1;
}

#define LEN 32
#define BUFSIZE 1024

int rec(rat * stack, int s_stack, rat * head, int len, char * buf)
{
  rat c[LEN];
  if(len == 0 && s_stack == 1)
    {
      printf("%3d/%2d:%s\n",stack->n, stack->d, buf);
      return 0;
    }
  if(len > 0)
    {
      char b[BUFSIZE];
      sprintf(b, "%s %d/%d", buf, head->n, head->d);
      memcpy(c, stack, LEN * sizeof(rat));
      pushrat(c + s_stack, head);
      rec(c, s_stack+1, head+1, len-1, b);
    }
  if(s_stack >= 2)
    {
      int i;
      rat * (*list[4]) (rat*,rat*,rat*) = {add,sub,mul,div};
      char ch[4] = "+-*/";
      for(i=0;i<4;i++)
        {
          char b[BUFSIZE];
          sprintf(b, "%s %c", buf, ch[i]);
          memcpy(c, stack, LEN * sizeof(rat));
          pushfunc(c + s_stack, list[i]);
          rec(c, s_stack-1, head, len, b);
        }
    }
  return 0;
}

void swap(rat *a, rat *b)
{
  rat c=*a;
  *a=*b;
  *b=c;
}

void perm(rat *c, int len, int n)
{
  int i;
  if(n==len)
    {
      rec(c,0,c,4,"");
      return;
    }
  for(i=n;i<len;i++)
    {
      swap(c+n,c+i);
      perm(c,len,n+1);
      swap(c+n,c+i);
    }
}

int main()
{
  rat c[LEN] = {{3,1},{3,1},{8,1},{8,1},{0,0}};
  perm(c, 4, 0);
}