Rosetta Code

User:Ledrug/bits: Difference between revisions

User page Discussion

User:Ledrug/bits (view source)

Revision as of 19:49, 12 September 2011

5,800 bytes removed ,  12 years ago
m
no edit summary
mNo edit summary
mNo edit summary
Line 132:
}
return (void*)-1;
}</lang>
<lang c>#include <stdio.h>
#include <string.h>
 
#define maxn 1000000
#define maxp 1000
int primes[maxp] = {2, 3}, n_primes = 2;
 
#ifdef KNUTH
char knuth[20000+2];
#endif
 
int show = 0;
void make_primes()
{
int i, n = 3, p;
while (n_primes < maxp) {
n += 2;
for (i = 0; i < n_primes; i++) {
p = primes[i];
if (n % p == 0) break;
if (p * p >= n) {
primes[n_primes++] = n;
break;
}
}
}
}
 
int length[maxn + 2] = {0, 0, 1, 2, 2};
 
int ones_(int n)
{
int r = 0;
while (n) {
if (1 & n) r++;
n >>= 1;
}
return r;
}
 
int lg2(int n)
{
int r = 0, i = 1;
while (i < n) r++, i *= 2;
return r;
}
 
int lb(int n)
{
int x = lg2(n);
return x - (n != (1 << x));
}
 
int seq_len(int n);
 
typedef struct { int out, sum, tail, l, u; } rec;
 
int iter;
int seq_insert(rec *x, int len, int p, int pos)
{
int j, i, min, max;
i = pos ? pos : seq_len(p);
 
while (i < len && p > x[i].u) i++;
 
if (i >= len || p < x[i].l) return 0;
iter++;
if (show) printf("insert %d %d\n", p, pos);
 
x[i].l = x[i].u = p;
x[i].out ++;
x[i].sum += len;
if (!x[len].tail || x[len].tail > p) x[len].tail = p;
 
#if 0
for (j = i + 1; j < len; j++) {
if (x[j].u > x[j-1].u * 2) x[j].u = x[j-1].u * 2;
if (x[j].l <= x[j-1].l) x[j].l = x[j-1].l + 1;
}
 
for (j = i - 1; j >= 2; j--) {
if (x[j].u >= x[j+1].u) x[j].u = x[j+1].u - 1;
if (x[j].l < x[j+1].l/2) x[j].l = x[j+1].l / 2;
}
#endif
min = max = i;
for (j = i; j < len && x[j+1].u > x[j].u * 2; j++)
x[j+1].u = x[j].u * 2;
if (max < j) max = j;
 
for (j = i; j < len && x[j+1].l <= x[j].l; j++)
x[j+1].l = x[j].l;
if (max < j) max = j;
 
for (j = i; i > 2 && x[j-1].u >= x[j].u; j--)
x[j-1].u = x[j].u - 1;
if (min > j) min = j;
 
for (j = i; i > 2 && x[j-1].l * 2 < x[j].l; j--)
x[j-1].l = (x[j].l + 1)/2;
if (min > j) min = j;
 
if (show) for (i = 0; i <= len; i++)
printf("(%d,%d)%s", x[i].l, x[i].u, i == len ? "\n": "->");
 
for (j = min; j < max; j++) if (x[j].u < x[j].l) return 0;
 
return 1;
}
 
void copy(rec *x, rec *n, int len)
{
memcpy(x, n, sizeof(rec) * len);
}
 
int seq_recur(rec *in, int len)
{
rec x[32];
int i, p, q, n, r, lim;
 
if (len < 2) return 1;
n = in[len].u;
 
if (in[len-1].u == in[len-1].l) {
if (n == in[len-1].u * 2 ||
n == in[len-1].u + 1 ||
n == in[len-1].u + 2)
if (seq_recur(in, len -1)) return 1;
}
 
if (show) {
printf("%d|", len);
for (i = 0; i <= len; i++)
printf("%d,%d%s", in[i].l, in[i].u, i == len ? "\n": " -> ");
}
 
 
if (n > in[len-1].u + in[len-2].u) {
if (n & 1) return 0;
if (seq_insert(in, len, n/2, len-1)) {
in[len-1].out++;
return seq_recur(in, len-1);
}
return 0;
}
 
//for (p = n/2, q = n - p; p; p--,q++) {
lim = 0;
if (in[len].out == 1) {
lim = in[in[len].sum].tail;
if (show)
printf("lim %d %d %d\n", len, in[len].sum, lim);
}
if (lim < 1) lim = 1;
 
//for (p = n/2, q = n - p; p >= lim; p--, q++) {
for (p = lim, q = n - p; p <= q; p++,q--) {
if (seq_len(q) >= len || p != q && seq_len(p) >= len)
continue;
 
// for (i = 0; i < len; i++) x[i] = in[i];
copy(x, in, 32);
 
r = len - 1;
 
if (x[len-1].u == x[len-1].l && x[len-1].u != q) r = 0;
if (show) printf("[%d] need %d %d\n", len, p, q);
if (seq_insert(x, len, q, r) && seq_insert(x, len, p, 0)
&& seq_recur(x, len - 1))
{
for (i = 0; i < len; i++) in[i] = x[i];
return 1;
};
}
return 0;
}
 
int seq(int n, int *in, int len)
{
int r, i;
rec x[32] = {{0}};
x[0].l = 1; x[1].l = 2; x[len].l = n;
x[0].u = 1; x[1].u = 2; x[len].u = n;
 
for (i = 2; i < len; i++) {
x[i].l = x[i - 1].l + 1;
x[i].u = x[i - 1].u << 1;
}
for (i = len - 1; i >= 2; i--) {
if (x[i].l * 2 < x[i + 1].l) x[i].l = (x[i + 1].l + 1) / 2;
if (x[i].u >= x[i+1].u) x[i].u = x[i+1].u - 1;
}
 
r = seq_recur(x, len);
if (r && show) {
printf("Success\n");
for (i = 0; i <= len; i++)
printf("%d,%d%s", x[i].l, x[i].u, i == len ? "\n": " -> ");
}
for (i = 0; i <= len; i++) in[i] = x[i].u;
 
return r;
}
 
int seq_len(int n)
{
int r, x[32], lb, l, u, i, j, o, ones[64];
 
if (length[n] || n <= 2) return length[n];
 
for (j = n, lb = -1, o = 0; j; j >>= 1, lb++)
if (j & 1) ones[o++] = lb;
 
u = lb + o - 1;
l = lb + lg2(o);
 
 
#if 0
for (i = 0; ; i++) {
r = primes[i];
if (r * r > n) break;
if (n % r) continue;
if (u > (j = seq_len(r) + seq_len(n / r))) u = j;
}
#else
for (i = 2; i * i <= n; i++) {
if (n % i) continue;
if (u <= (j = seq_len(i))) continue;
if (u > (j += seq_len(n / i))) u = j;
}
#endif
if (l == u) goto done;
 
// if (u > (j = seq_len(n - 1) + 1)) u = j;
// if (l == u) goto done;
 
if (o <= 3) l = u;
else if (o == 4) {
i = ones[3] - ones[2], j = ones[1] - ones[0];
if (i == j || i == j + 1 ||
(j == 1 && (i == 3 || (i == 5 && ones[2] == ones[1] + 1))))
u = lb + 2;
}
else {
iter = 0;
while (l < u) {
if (!seq(n, x, l)) l++;
else {
printf("lower: %d %d %d\n", n, l, u - l);
u = l;
}
}
printf("iter %d %d\n", n, iter);
}
done:
length[n] = u;
 
#ifdef KNUTH
if (u != knuth[n])
printf("######### disc: %d %d %d\n", n, l, knuth[n]);
#endif
 
// printf("%d %d %d\n", n, l, u);
// fflush(stdout);
 
return u;
}
 
void pb(int n)
{
int x = 1;
while (x <= n) {
putchar((x & n) ? '#':'-');
x <<= 1;
}
putchar('\n');
}
 
int yy[] = {1, 2, 4, 8, 16, 32, 64, 128, 129, 257, 340, 514, 771, 1111};
int main()
{
int i, j, t, top, x[32];
make_primes();
int total = 0;
 
#ifdef KNUTH
FILE *fp = fopen("out", "r");
knuth[0] = 32;
fread(knuth + 1, 1, 20000, fp);
fclose(fp);
for (i = 0; i < 20001; i++) knuth[i] -= 32;
#endif
 
show = 0;
top = 11129;
for (i = 0; i < top; i++) {
seq(i, x, t = seq_len(i));
printf("== %d ==\n", i);
pb(i);
for (j = 0; j <= t; j++) pb(x[j]);
putchar('\n');
total += iter;
}
 
printf("%d\n", total);
return 0;
}</lang>
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/196665"