Игорь Пашев - Re: Арифметика для взрослых

(Recent Entries) (Archive) (Friends) (User Info)

Nov. 30th, 2008

01:43 am - Re: Арифметика для взрослых

Previous Entry Add to Memories Tell A Friend Next Entry

http://lj.rossia.org/users/neklyueva/686169.html


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

unsigned int N = 1;
unsigned int t = 0;
unsigned int b = 3; /* основание */
unsigned int i;
char*        str;
const char   digits[] =
    {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};


/* a^n */
unsigned int upow(unsigned int a, unsigned int n)
{
    unsigned int i, r = 1;
    for (i = 0; i < n; i++) r *= a;
    return r;
}

/* buf - куда поместить строку, N - число разрядов,
base - основание системы, u - исходное число */
void uint2str(char* buf, unsigned int N, unsigned int base, unsigned int u)
{
    unsigned int i;
    for (i = 1; i <= N; i++)
    {
        buf[N-i] = digits[u % base];
        u /= base;
    }
}

int main(int argc, char **argv)
{
    if (argc > 1) sscanf(argv[argc - 1], "%u", &N);
    str = malloc(sizeof(char)*(N + 1));
    str[N + 1] = '\0';

    for (i = 0; i < upow(b, N); i++)
    {
        uint2str(str, N, b, i);
        if (!strstr(str, "22"))
        {
            printf("%s = %u\n", str, i);
            t++;
        }
    }

    free(str);
    printf("N = %u, t = %u\n", N, t);
    return 0;
}

Для N=4, например
0000 = 0
0001 = 1
0010 = 2
0100 = 4
0101 = 5
1000 = 8
1001 = 9
1010 = 10
N = 4, t = 8

Tags: , ,
(7 комментариев | Оставить комментарий)

Comments:

[User Picture]
From:[info]igorpashev
Date:November 30th, 2008 - 01:05 am
(Link)
После равенства: десятичная, восьмеричная,
шестнадцатеричная записи —
интересно, что в последней есть цифры только до "A";
а в восьмеричной должны отсутствовать семёрки (111),
тройки (011) и шестёрки (110) — их действительно не видно:
...
10101010000100000101 = 696581, 2520405, AA105
10101010000100001000 = 696584, 2520410, AA108
10101010000100001001 = 696585, 2520411, AA109
10101010000100001010 = 696586, 2520412, AA10A
10101010000100010000 = 696592, 2520420, AA110
10101010000100010001 = 696593, 2520421, AA111
10101010000100010010 = 696594, 2520422, AA112
10101010000100010100 = 696596, 2520424, AA114
10101010000100010101 = 696597, 2520425, AA115
10101010000100100000 = 696608, 2520440, AA120
10101010000100100001 = 696609, 2520441, AA121
10101010000100100010 = 696610, 2520442, AA122
10101010000100100100 = 696612, 2520444, AA124
10101010000100100101 = 696613, 2520445, AA125
(Reply to this)
[User Picture]
From:[info]igorpashev
Date:November 30th, 2008 - 03:48 pm
(Link)
Похоже на последовательности Фибоначчи:

N=1: 2
N=2: 3
N=3: 5
N=4: 8
N=5: 13
N=6: 21
N=7: 34

А значит элементарную формулу вряд ли можно написать.
(Reply to this) (Thread)
[User Picture]
From:[info]igorpashev
Date:November 30th, 2008 - 03:54 pm
(Link)
Доказать, наверно, можно по индукции.
(Reply to this) (Parent)
From:[info]666
Date:November 30th, 2008 - 04:40 pm
(Link)
что-то большая программа, она попроще пишется

while(++$n)
{
for($i = $x = 0; $i < 1<<$n; $i++)
{
$x += sprintf("%b",$i) !~ /11/;
}
$|=1; print "$x ";
}
(Reply to this) (Thread)
[User Picture]
From:[info]igorpashev
Date:November 30th, 2008 - 05:19 pm
(Link)
Ну, да,
на ассемблере она ещё длиннее (163 строки) :-)

«В одной строке shell больше духа UNIX, чем в тысяче строк C»
(Reply to this) (Parent)
[User Picture]
From:[info]igorpashev
Date:November 30th, 2008 - 05:25 pm
(Link)
Оказывается это крепко связано с Фибоначчиевой системой счисления.

Столько всего интересного...
(Reply to this)
[User Picture]
From:[info]igorpashev
Date:December 1st, 2008 - 01:35 pm
(Link)
Проверил для троичной системы:
Числа без 11:     Числа без 22:
N = 1, t = 3      N = 1, t = 3
N = 2, t = 8      N = 2, t = 8
N = 3, t = 22     N = 3, t = 22
N = 4, t = 60     N = 4, t = 60
N = 5, t = 164    N = 5, t = 164
N = 6, t = 448    N = 6, t = 448
N = 7, t = 1224   N = 7, t = 1224
N = 8, t = 3344   N = 8, t = 3344
N = 9, t = 9136   N = 9, t = 9136


Числа без 11, 22:
N = 1, t = 3
N = 2, t = 7
N = 3, t = 17
N = 4, t = 41
N = 5, t = 99
N = 6, t = 239
N = 7, t = 577
N = 8, t = 1393
N = 9, t = 3363

Числа без 11, 22, 12, 21:
N = 1, t = 3
N = 2, t = 5
N = 3, t = 11
N = 4, t = 21
N = 5, t = 43
N = 6, t = 85
N = 7, t = 171
N = 8, t = 341
N = 9, t = 683
(Reply to this)