0 / 0 / 0
Регистрация: 06.01.2018
Сообщений: 13
1

Дана последовательность 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1

06.01.2018, 12:38. Показов 3878. Ответов 22
Метки нет (Все метки)

Есть такая задача. Дана бесконечная последовательность. 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 и т.д. Вводится число n. Надо вывести какое число стоит на этом месте. Главная проблема в том, что n ≤10500000. Напишите, пожалуйста, код, который будет работать хотя бы для n>1020
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.01.2018, 12:38
Ответы с готовыми решениями:

Дана последовательность, элементы которой есть целые двузначные числа. Упорядочить последовательность по убыванию произведений цифр
Здравствуйте. На форуме есть код подобный, но по возрастанию сумм элементов. Как мне подправить...

Дана последовательность
Дана последовательность с 40 целых чисел, заполнена в промежутке . Найти в последовательности...

Дана последовательность
24. Даны действительные числа A1; А2;...; А2n. Получить; a. A1; An+1; А2; An+1; ...; Аn; А2n;...

Дана последовательность из М чисел
Дана последовательность из М чисел. Вычислить произведение и количество чисел, которые меньше 10.

22
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
07.01.2018, 02:21 21
Цитата Сообщение от Байт Посмотреть сообщение
(double)n
Люблю писать 1.0 * n правда до сих пор не знаю насколько это хорошо. В С++ вообще рекомендуют static_cast...
Цитата Сообщение от Байт Посмотреть сообщение
Если хочешь поразмять мозги - конечно Второй.
Да, это лучше чем тупо копипастить. Но извлечение корня это уже круче чем сложение / умножение, реализовать такое эффективно тяжело.
0
298 / 207 / 174
Регистрация: 11.05.2016
Сообщений: 655
07.01.2018, 06:21 22
Накалякал с длинной, максимальное число влезет порядка 10^80;
Код попозже причешу / выложу, а то уж лень и спать пора давно)
Миниатюры
Дана последовательность 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1   Дана последовательность 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1  
0
298 / 207 / 174
Регистрация: 11.05.2016
Сообщений: 655
07.01.2018, 15:38 23
работает, но неправильно)
Архитектура кода изяществом не блещет, целью было поиграть в длинный велосипед

main.cpp
Кликните здесь для просмотра всего текста
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
#include "inc.h"
#include "temp.h"
#include "foos.h"
 
 
const int SoLong::cellsize = 8;
const int SoLong::maxsize = 10;
 
void find_in(SoLong &n)
{
    int two = 2;
    SoLong how = sqrt(n);
    how = how*two;
    ++how;
    SoLong max = how/2;
    n=n-(max*max);
 
    ( n<=max ? ++n : n=how-n );
}
 
int main()
{
 
    SoLong a;
    a.input();
    
    find_in(a);
    std::cout << "\n Result: ";
    show(a);
 
    system("pause");
    return(0);
}

temp.h
Кликните здесь для просмотра всего текста
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
#include "inc.h"
 
#ifndef _TEMP_H_
#define _TEMP_H_
 
class SoLong {
private:
    //std::vector<int> number;
    static const int cellsize;
    static const int maxsize;
 
    int arr[10];
    int amount;
 
public:
 
    SoLong()
    {
    //  number.reserve(10);
        memset(arr,0,sizeof(arr));
        amount = 9;
    }
 
    void setAmount()
    {
        int pos = 0;
        while (!arr[pos]) pos++;
        amount = pos-1;
    }
    //~~~~~~~~~~~~~~~~~~~~~~~~~~~//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//
    //input/output
 
    void input()
    {
        std::string str;
 
        std::cin >> str;
 
        int pos = maxsize-1;
        for (int i=str.size()-1;i>=0;i-=cellsize)
        {
          int start = i - cellsize + 1;
          if (start<0) start = 0;
          std::string dig = str.substr(start,i-start+1);
          arr[pos--] = stoi(dig);
        }
        amount = pos;
    }
 
    void show()
    {
        bool zero_shift = true;
        for(int i=0; i<maxsize; i++)
        {
            if(arr[i]) zero_shift = false;
            if(!zero_shift) 
            {
                std::cout << std::setw(this->cellsize) << std::setfill('0') << arr[i] << " ";
            }
        }
    }
 
    friend void show(SoLong &a);
 
    //*******
    //compare
    friend bool operator>(SoLong &a, SoLong &b);
    friend bool operator>=(SoLong &a, SoLong &b);
    friend bool operator<(SoLong &a, SoLong &b);
    friend bool operator<=(SoLong &a, SoLong &b);
    friend bool operator==(SoLong &a, SoLong &b);
    //******************************************
    //+-/*sqrt
    SoLong &operator=(SoLong &another)
    {
        memcpy(this->arr,another.arr, sizeof(int)*this->maxsize);
        this->amount = another.amount;
 
        return *this;
    }
 
    friend SoLong sqrt(SoLong &a);
 
    friend SoLong operator*(SoLong &a, int b);
    friend SoLong operator*(SoLong &a, SoLong &b);
    
    friend SoLong operator/(SoLong &a, int n);
    friend SoLong operator-(SoLong &a, SoLong &b);
    friend SoLong operator++(SoLong &a);
 
 
};
 
#endif

temp.cpp
Кликните здесь для просмотра всего текста
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include "inc.h"
#include "temp.h"
 
void show(SoLong &a)
{
    a.show();
}
 
bool operator>(SoLong &a, SoLong &b)
{
    if(a.amount < b.amount) return true;
    if(a.amount > b.amount) return false;
    for(int i=a.amount; i<a.maxsize; i++)
    {
        if(a.arr[i] > b.arr[i]) return true;
        if(a.arr[i] < b.arr[i]) return false;
    }
    return false;
}
 
bool operator>=(SoLong &a, SoLong &b)
{
    if(a.amount < b.amount) return true;
    if(a.amount > b.amount) return false;
    for(int i=a.amount; i<a.maxsize; i++)
    {
        if(a.arr[i] > b.arr[i]) return true;
        if(a.arr[i] < b.arr[i]) return false;
    }
    return true;
}
 
bool operator<(SoLong &a, SoLong &b)
{
    if(a.amount > b.amount) return true;
    if(a.amount < b.amount) return false;
    for(int i=a.amount; i<a.maxsize; i++)
    {
        if(a.arr[i] < b.arr[i]) return true;
        if(a.arr[i] > b.arr[i]) return false;
    }
    return false;
}
 
bool operator<=(SoLong &a, SoLong &b)
{
    if(a.amount > b.amount) return true;
    if(a.amount < b.amount) return false;
    for(int i=a.amount; i<a.maxsize; i++)
    {
        if(a.arr[i] < b.arr[i]) return true;
        if(a.arr[i] > b.arr[i]) return false;
    }
    return true;
}
 
bool operator==(SoLong &a, SoLong &b)
{
    if(a.amount > b.amount) return false;
    if(a.amount < b.amount) return false;
    for(int i=a.amount; i<a.maxsize; i++)
    {
        if(a.arr[i] < b.arr[i]) return false;
        if(a.arr[i] > b.arr[i]) return false;
    }
    return true;
}
 
SoLong operator*(SoLong &a, SoLong &b)
{
    SoLong res;
 
    for (int i=a.maxsize-1; i>a.amount;i--)
    {
        double r = 0, rr = 0;
        for (int j=b.maxsize-1; j>b.amount; j--)
        {
            int temp = i + j - a.maxsize+1;
            double sotemp = (double)a.arr[i] * (double)b.arr[j];
 
            int x = temp;
            while(sotemp && x >=0)
            {
                sotemp += res.arr[x];
                r = floor(sotemp * 0.00000001);
                res.arr[x] = sotemp - floor(r)*100000000;
                sotemp = r;
                x--;
            }
 
        }
    }
 
    res.setAmount();
 
    return res;
}
 
SoLong operator*(SoLong &a, int b)
{
    SoLong res;
 
    for (int i=a.maxsize-1; i>a.amount;i--)
    {
        double r = 0, rr = 0;
 
            
            double sotemp = (double)a.arr[i] * b;
 
            int x = i;
            while(sotemp && x >=0)
            {
                sotemp += res.arr[x];
                r = floor(sotemp * 0.00000001);
                res.arr[x] = sotemp - floor(r)*100000000;
                sotemp = r;
                x--;
            }
 
    }
    
 
    res.setAmount();
 
    return res;
}
 
SoLong sqrt(SoLong &a)
{
    SoLong cur;
 
    int pos = (a.maxsize+a.amount-1)/2;
    cur.amount = pos;
    pos++;
    while (pos<cur.maxsize)
    {
        int l = 0, r = 99999999;
        int curDigit = 0;
        while (l<=r)
        {
            int m = (l+r)>>1;
            cur.arr[pos] = m;
            if ((cur * cur) <= a)
            {
 
                curDigit = m;
                l = m + 1;
            }
            else r = m - 1;
        }
        cur.arr[pos] = curDigit;
        pos++;
    }
//  cur.setAmount();
    return cur;
 
}
 
SoLong operator/(SoLong &a, int n)
{
  SoLong res;
  res.amount = a.amount;
  int ost = 0;
  for (int i=res.amount;i<res.maxsize;i++)
  {
    int cur = ost * 100000000 + a.arr[i];
    res.arr[i] = cur / n;
    ost = cur % n;
  }
 
  res.setAmount();
  return res;
}
 
SoLong operator-(SoLong &a, SoLong &b)
{
    SoLong  res = a;
    int r = 0;
    for (int i = res.maxsize-1; i>=res.amount; i--)
    {
        res.arr[i] -= b.arr[i] + r;
        if (res.arr[i]<0)
        {
            res.arr[i]+=100000000;
            res.arr[i-1]--;
        }   
    }
    res.setAmount();
 
    return res;
}
 
SoLong operator++(SoLong &a)
{
    int x = a.maxsize-1;
 
    while(a.arr[x] == 99999999)
    {
        a.arr[x] = 0;
        x--;
    }
    a.arr[x]++;
 
    return a;
 
}


Умножение собрано из картона и костылей, скрепленных соплями; как будет лучше править?
От переполнения защиты нет
В отдельности по арифметике ошибок не замечено

Основная проблема: на числах 99~99, начиная от 16 знаков проскакивает 0 и 99~98 выдает 1,
хотя должно же быть 99~98 = 2, 99~99=1;
В первую очередь, наверное, стоит переписать сам алгоритм, хотя может для моего замыленного глаза сейчас очевидное не очевидно
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.01.2018, 15:38
Помогаю со студенческими работами здесь

Дана вещественная последовательность...
Дана последовательность из n вещественных чисел. Первое число в последовательности нечетное. Найти...

Дана последовательность из n символов
Дана последовательность из n символов и k &lt;= n, из данной последовательности нужно выбрать k...

Дана последовательность чисел a1, a2,...,an
Указать наименьшую длину числовой оси содержащую все эти числа.

Дана последовательность чисел
Добрый день. В условии сказано: Дано: натуральные u, v, действительные B1, …, Buv . Подскажите...


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

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru