プログラマ専用SNS ミクプラ

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>


#define MAXCOEFFS 100
#define LBUFSIZE  2048
#define SBUFSIZE  256

#define TRUE      1
#define FALSE     0

#define MOD_P     2



struct poly_s {
  int coeff[MAXCOEFFS];
  int deg;
};

void setpoly_by_value(struct poly_s *a, int value)
{
  int k;

  for (k = 0; value > 0; k++) {
    if (k >= MAXCOEFFS) {
      fprintf(stderr, "error: too large degree\n");
      exit(2);
    }
    a->coeff[k] = value % MOD_P;
    value = (int)(value / MOD_P);
  }
  
  a->deg = k - 1;
}

void setpoly_by_string(struct poly_s *a, char *string)
{
  int k;
  int count, maxk;

  if (string[0] == '0') {
     int value;

     value = (int)strtoul(string + 1, NULL, 8);
     setpoly_by_value(a, value);

  } else if (strchr(string, ',') != NULL) {
    char *p;
    int tmpbuf[MAXCOEFFS];
    count = 0;
    maxk = -1;
    p = strtok(string, ",");
    while (p) {
      tmpbuf[count] = atoi(p);
      count++;
      p = strtok(NULL, ",");
    }
    for (k = 0; k < count; k++) {
      a->coeff[k] = tmpbuf[count - k -1];
      if (a->coeff[k] != 0) {
        maxk = k;
      }
    }
    a->deg = maxk;
  } else {
    count = strlen(string);
    maxk = -1;
    for (k = 0; k < count; k++) {
      if (k >= MAXCOEFFS) {
        fprintf(stderr, "error: too large degree\n");
        exit(2);
      }
      if (isdigit(string[count - k - 1])) {
        a->coeff[k] = (string[count - k -1] - '0');
        if (a->coeff[k] != 0) {
          maxk = k;
        }
      } else {
        a->coeff[k] = 0;
      }
    }
    a->deg = maxk;
  }
}

char *strpoly(struct poly_s *a)
{
  int i;
  int count;
  char tmpbuf[SBUFSIZE];
  static char localbuf[LBUFSIZE];

  count = 0;
  for (i = a->deg; i >= 0; i--){
    if (a->coeff[i] !=0){
      if (count == 0) {
        localbuf[0] = '\0';
      } else {
        strcat(localbuf, " + ");
      }
      if (a->coeff[i] == 1) {
        sprintf(tmpbuf, "x^%d", i);
      } else {
        sprintf(tmpbuf, "%d x^%d", a->coeff[i], i);
      }
      strcat(localbuf, tmpbuf);
      count++;
		}
  }
  if (count == 0) {
    strcpy(localbuf, "0");
  }
  return (localbuf);
}

void polydiv(struct poly_s *a, struct poly_s *b, struct poly_s *q, struct poly_s *r)
{
  int i, j;
	int k = 0, l = 0;
	int m = 0, n = 0;
	int o = 0, p = 0;

	q->deg = a->deg - b->deg;
	if (q->deg < 0) {
	  q->deg = -1;
	}

	for (i = 0;i <= a->deg;i++) {
		k += a->coeff[i] * (int)pow((double) MOD_P, (double) i);
	}
	for (j = 0;j <= b->deg;j++) {
		l += b->coeff[j] * (int)pow((double) MOD_P, (double) j);
	}
	
	m = k / l;
	n = k % l;

	for (i = 0;i <= 10;i++) {
		r->coeff[i] = 0;
		q->coeff[i] = 0;
	}
	
	while (m > 0) {
		q->coeff[o] = m % MOD_P;
		m = m / MOD_P;
		o++;
	}
	while (n > 0) {
		r->coeff[p] = n % MOD_P;
		n = n / MOD_P;
		p++;
	}
}


void polycalc(char *s1, char *s2)
{
  struct poly_s a, b, c, d, r, q;

  setpoly_by_string(&a, s1);
  setpoly_by_string(&b, s2);

  printf("=== Operation over GF[%d] ===\n", MOD_P);
  printf("\n");
  printf("deg a(x) = %d, a(x) = %s\n", a.deg, strpoly(&a));
  printf("deg b(x) = %d, b(x) = %s\n", b.deg, strpoly(&b));
  printf("\n");

　polydiv(&a, &b, &q, &r);

  printf("q + r = a / b\n");
  printf("deg q(x) = %d, q(x) = %s r(x) =%s\n", q.deg, strpoly(&q), strpoly(&r));
  printf("\n");
}　

int main(int argc, char **argv)
{
  if (argc != 3) {
    fprintf(stderr, "usage: polycalc <string1><string2>\n");
    fprintf(stderr, "ex. polycalc 1011001 1101\n");
    fprintf(stderr, "ex. polycalc o23 1,1,0,1\n");
    exit(2);
  }
  
  polycalc(argv[1], argv[2]);
  
  return (0);
}
 

コード:

polycalc o23 1,1,0,1

コード:

polycalc 1011101 1001

コード:

=== Operation over GF[2] ===

deg a(x) = 6, a(x) = x^6 + x^4 + x^3 + x^0
deg b(x) = 3, b(x) = x^3 + x^2 + x^0

q + r = a / b
deg q(x) = 3, q(x) = x^2 + x^1 r(x) =x^3 + x^1 + x^0

コード:

=== Operation over GF[2] ===

deg a(x) = 6, a(x) = x^6 + x^4 + x^3 + x^0
deg b(x) = 3, b(x) = x^3 + x^2 + x^0

q + r = a / b
deg q(x) = 3, q(x) = x^2 + x^1 r(x) =x^2 + x^1