genetic.c

Ulm大学2003-2004年竞赛题

/* Problem   Genetic Code
 * Algorithm Backtracking
 * Runtime   O(3^n)
 * Author    Walter Guttmann
 * Date      12.03.2003
 */

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

char s[8192], *end=s, *target=s+5000;

int isThue()
{
  int len;
  for (len=1 ; end-len-len>=s ; len++)
    if (strncmp(end-len-len, end-len, len) == 0)
      return 0;
  return 1;
}

int backtrack()
{
  if (end == target)
    return 1;
  ++end;
  for (end[-1]='N' ; end[-1]<='P' ; end[-1]++)
    if (isThue() && backtrack())
      return 1;
  --end;
  return 0;
}

int main()
{
  int n;
  FILE *in = fopen("genetic.in", "r");
  backtrack();
  while (fscanf(in, " %d ", &n) == 1)
  {
    if (n == 0) break;
    assert(1 <= n && n <= 5000);
    printf("%.*s\n", n, s);
  }
  fclose(in);
  return 0;
}