Форум программистов, компьютерный форум CyberForum.ru

[Длинная арифметика]Обращение к большому индексу - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.05.2011, 10:40     [Длинная арифметика]Обращение к большому индексу #1
Бесконечная последовательность битов, предложенная Кеане, равна 001001110001001110110110001… и формируется следующим алгоритмом: вначале записывается 0, потом 001, далее 001001110, то есть, для получения следующего члена, предыдущий записывается дважды, а справа приписывается его отрицание. Элементы этого ряда являются начальными подпоследовательностями Кеане.

Требуется написать программу, которая по заданному n определит N-й бит этой последовательности.
Входные данные

Входной файл INPUT.TXT содержит число N (N <= 10^200).
Выходные данные

В выходной файл OUTPUT.TXT должен содержать найденный бит.
Я реализовал собственно эту последовательность, вроде даже работает, и завис на том, как вывести нужный элемент.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <sstream>
typedef std::string::iterator si;
short compare(std::string a, std::string b) {
    if (a.size() > b.size())
        return 1;
    if (a.size() < b.size())
        return 2;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] > b[i])
            return 1;
        if (a[i] < b[i])
            return 2;
    }
    return 0;
 
}
 
int main() {
    std::string a(1, '0'), b, N;
    std::cin >> N;
    std::string size;
    while (compare(N, size) == 1) { // пока размер массива меньше N
        b = a;
        a += b;
        for (si i = b.begin(); i != b.end(); i++) //инверсия b
            if (*i == '1')
                * i = '0';
            else
                *i = '1';
        a += b;
    std::ostringstream ost;
    ost << a.size();
    size = ost.str();
    }
    //std::cout << a[N-1];
    return 0;
}
И вообще, влезет ли эта последовательность в std::string?
Если не влезет, то как тогда решается эта задача?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.05.2011, 10:40     [Длинная арифметика]Обращение к большому индексу
Посмотрите здесь:

C++ Длинная арифметика
C++ Длинная арифметика))
Длинная арифметика C++
C++ Длинная арифметика
C++ Длинная арифметика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
08.05.2011, 10:43     [Длинная арифметика]Обращение к большому индексу #2
Нет, не влезет.
Тут, очевидно, олимпиадная задача. Нужно без создания самой последовательности сообразить, чему будет равен N-й бит.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.05.2011, 11:00  [ТС]     [Длинная арифметика]Обращение к большому индексу #3
Вообще эта задача из раздела длинная арифметика...
Я записал первые 1000 бит в файл, никакой закономерности там не нашел, да ее и не должно быть...
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
08.05.2011, 11:04     [Длинная арифметика]Обращение к большому индексу #4
Цитата Сообщение от diagon Посмотреть сообщение
Вообще эта задача из раздела длинная арифметика...
Я записал первые 1000 бит в файл, никакой закономерности там не нашел, да ее и не должно быть...
Есть. Потому как последовательность создается не случайным способом, а по четкому алгоритму: каждое следующее - в три раза длиннее предыдущего. Отсюда и надо плясать.
То есть размер вычисляется так:
Код
D = 1 + 1*3 + 1*3*3 + 1*3*3*3 +...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.05.2011, 11:16  [ТС]     [Длинная арифметика]Обращение к большому индексу #5
Что-то не очень понял, при чем здесь размер...
Может сделать так:
C++
1
std::vector <std::string>
в 1 элементе 0, во втором 001 и тд.
Возможно тогда она в стринги и влезет...
ValeryLaptev
Эксперт C++
1005 / 784 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
08.05.2011, 13:19     [Длинная арифметика]Обращение к большому индексу #6
Цитата Сообщение от diagon Посмотреть сообщение
Что-то не очень понял, при чем здесь размер...
Может сделать так:
C++
1
std::vector <std::string>
в 1 элементе 0, во втором 001 и тд.
Возможно тогда она в стринги и влезет...
Не влезет!
N = 10^200! F виртуальной памяти всего 4 миллиарда байтов - это 10^10.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.05.2011, 20:50     [Длинная арифметика]Обращение к большому индексу
Еще ссылки по теме:

C++ Длинная арифметика
C++ Длинная арифметика
Длинная арифметика C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
eXXXXXXXXXXX
30 / 30 / 3
Регистрация: 24.02.2011
Сообщений: 126
08.05.2011, 20:50     [Длинная арифметика]Обращение к большому индексу #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <fstream>
using namespace std;
const int N=421;
ifstream in("INPUT.TXT");
ofstream out("OUTPUT.TXT");
char *div(char *s,int length,char *t,int *mod)
{
    int ind=0,curnum=0,indt=0;
    t[0]='0';
    t[1]=0;
    if ((s[0]-'0')<3)
    {
        if (length==1)
        {
            *mod=s[0]-'0';
            return t;
        }
        else
        {
            curnum=(s[0]-'0')*10+s[1]-'0';;
            ind=1; 
        }
    }
    else
        curnum=s[0]-'0';
    for(;;)
    {
        t[indt++]=(curnum)/3+'0';
        ind++;
        if (ind==length)
            break;
        curnum=(curnum%3)*10+s[ind]-'0';     
    }
    t[indt]=0;
    *mod=curnum%3;
    return t;
}
char *to3(char *s)
{
    char *t=new char[N],*tmp=new char[N];;
    int l=0,mod;
    while(s[0]!='0')
    {
        div(s,strlen(s),tmp,&mod);
        strcpy(s,tmp);
        t[l++]=mod+'0';
    }
    t[l]=0;
    strrev(t);
    strcpy(s,t);
    delete[] tmp;
    delete[] t;
    return t;
}
char *dec(char *s)
{
    int ost;
    int tmp;
    char t[N];
    if (s[strlen(s)-1]=='0')
    {
        s[strlen(s)-1]='9';
        s[strlen(s)-2]--;
    }
    else
    {
        s[strlen(s)-1]--;
        return s;
    }
    for (int i=strlen(s)-2;i>=0;i--)
    {
        tmp=s[i]-'0';
        if (tmp<0)
        {
            s[i-1]--;
            s[i]='9';
        }
    }
    int j=0;
    while(s[j++]=='0')
        ;
    j--;
    strcpy(t,s+j);
    strcpy(s,t);
    return s;
}
int main()
{
    char s[N];
    int var=0;
    in>>s;
    dec(s);
    to3(s);
    int len=strlen(s);
    for (int i=0;i<len;i++)
    {
        if (s[i]=='2')
            var^=1;
    }
    out<<var;
return 0;
}
Вот код, решение основывается на переводе чисел в 3-ую с.с. Например при нумерации от 0
0..22 - первый сегмент
100..122 - второй сегмент
200..222 - третий сегмент
Короче если разобраться то при нечетном кол-ве двоек 1 иначе 0. Если разбирать это троичное число от начала, то 0 - 1 сегмент, 1 - 2 сегмент , 2- 3 сегмент, дальше убираем первую цифру, и снова 0 - 1 сегмент, 1 - 2 сегмент , 2- 3 сегмент и т.д., доходим до 0, а для нуля - бит 0.
Yandex
Объявления
08.05.2011, 20:50     [Длинная арифметика]Обращение к большому индексу
Ответ Создать тему
Опции темы

Текущее время: 00:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru