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
62 / 50 / 39
Регистрация: 03.01.2017
Сообщений: 133
06.01.2018, 15:47 2
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
#include <iostream> 
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
 
using namespace std;
 
int main()
{
    setlocale( LC_ALL,"Russian" );
    
    while(1)
    {
        int i, j, k=1, q=0, n=1, a, stop=0;
        int mas2;
        int l=0, sum=0, sum2=0, sum3=0;
        
        cout << "\npress 0 for end;\nwrite n for 1-oo: "; cin >> n; if(n == 0) break;
        n-=1;
        
        while(1)
        {
            //cout << "\n";
            q = k+k-1;
            sum += q;
        
            if(stop != 1)
                if(sum < n)
                {
                    //printf("%d-[%d] ",k,q);
                    sum2 += q;
                    //printf("(%d) ",sum2);
                }
                else
                {
                    //printf("%d+[%d] ",k,q);
                    sum3 = n - sum2;
                    //printf("(%d) ",sum3);
        
                    for (i = 1; i <= k-1; i++)
                    {
                        //printf(" %d",i);
                        if(l == sum3) { mas2 = i; break; } else l++;
                    }
                    
                    //printf(" %d",k);
                    if(l == sum3) { mas2 = i; break; } else l++;
                
                    for (i = k-1; i > 0; i--)
                    {
                        //printf(" %d",i);
                        if(l == sum3) { mas2 = i; break; } else l++;
                    }
            
                    stop++;
                }
                else break;
        
            k++;
        }
        cout << "ANSWER = " << mas2 << "\n\n";
    }
    
    system("Pause");
    return 0;   
}
0
0 / 0 / 0
Регистрация: 06.01.2018
Сообщений: 13
06.01.2018, 16:02  [ТС] 3
Я написал такой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
    long long int i=1,s=1,sb,n;
    cin>>n;
    while(s<n){
        i++;
        sb=s;
        s=s+i*2-1;
    }
    if (n-sb>i) cout<<s-n+1; else cout<<n-sb;
    return 0;
}
Вот только есть ограничение в 6 сек. И этот код работает нормально до 1010. Как мне его оптимизировать?
0
Диссидент
Эксперт C
26856 / 16758 / 3675
Регистрация: 24.12.2010
Сообщений: 37,521
06.01.2018, 16:20 4
Maksat32, я не очень понял закон образования твоего ряда. Но вот что заметил. В строчке 13 ты прибавляешь очередное нечетное число. Т.е. s = сумме нечетных чисел от 1 до 2*i -1. Но значение этой суммы давно известно. Это будет i2 (доказать можно по индукции или как сумму арифметической прогрессии)
Значит тебе нужно подсчитать корень квадратный из n (с недостатком)
Правда, что делать с такими большими числами, я не знаю...
0
298 / 207 / 174
Регистрация: 11.05.2016
Сообщений: 655
06.01.2018, 16:40 5
Цитата Сообщение от Байт Посмотреть сообщение
Правда, что делать с такими большими числами, я не знаю...
шифровать инвентарные номера атомов обозримой вселенной с запасом на несколько миллиардов лет, очевидно же)
0
0 / 0 / 0
Регистрация: 06.01.2018
Сообщений: 13
06.01.2018, 16:50  [ТС] 6
Байт, мой код ищет к какому блоку принадлежит номер N(блоки: 1, 1 2 1, 1 2 3 2 1 и т.д.). Потом, относительно наибольшего числа в этом блоке(число I), я нахожу, какое число стоит под индексом N.
0
Диссидент
Эксперт C
26856 / 16758 / 3675
Регистрация: 24.12.2010
Сообщений: 37,521
06.01.2018, 16:59 7
Цитата Сообщение от Herji Посмотреть сообщение
шифровать инвентарные номера атомов обозримой вселенной с запасом на несколько миллиардов лет,
Тем не менее для хорошей длинной арифметики эта задача вполне по силам. Ведь речь о последовательностях порядка 50000 интов или 200000 байт, что при памяти современных компьютеров - сущие пустяки.

Добавлено через 3 минуты
Цитата Сообщение от Maksat32 Посмотреть сообщение
Байт, мой код ищет к какому блоку принадлежит номер N(блоки: 1, 1 2 1, 1 2 3 2 1 и т.д.). Потом, относительно наибольшего числа в этом блоке(число I), я нахожу, какое число стоит под индексом N.
Да, это я понял. Но ведь k-й блок у вас имеет длину 2k-1, так? Значит общая длина k блоков есть k2Вот именно это я и хотел сказать...

Добавлено через 2 минуты
Цитата Сообщение от Maksat32 Посмотреть сообщение
блоки: 1, 1 2 1, 1 2 3 2 1 и т.д.)
Да, теперь понял закон. k-блок выглядит так: 1 2 3 .. k ..3 2 1, угадал?
0
3660 / 2997 / 828
Регистрация: 25.03.2012
Сообщений: 11,045
Записей в блоге: 1
06.01.2018, 17:30 8
CopBuroJLoBa, как ты так быстро решил задачу? Тут я даже задание до конца не понял, пока ниже не объяснили про блоки! А ты как???
0
298 / 207 / 174
Регистрация: 11.05.2016
Сообщений: 655
06.01.2018, 17:30 9
Получается количество чисел в искомом блоке 1+2*n^0.5
0
0 / 0 / 0
Регистрация: 06.01.2018
Сообщений: 13
06.01.2018, 17:43  [ТС] 10
Как мне реализовать программу для очень большого n (n≤10500)
0
62 / 50 / 39
Регистрация: 03.01.2017
Сообщений: 133
06.01.2018, 19:27 11
Kuzia domovenok, здесь есть последовательность: "1", "121", "12321", в которой можно создать условие "если", позволяющее не нагружать программу до основного подсчета элементов. Сначала посчитается суммарное число элементов меньших искомого "n". Если сумма превышает "n", нужная последовательность найдена, выполняется условие "иначе", для поиска нужной переменной. Если убрать комментарии у выводов, станет проще.
0
298 / 207 / 174
Регистрация: 11.05.2016
Сообщений: 655
06.01.2018, 20:27 12
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
#include <iostream>
#include <cmath>
 
void find_in(int &n)
{
    int how = sqrt((double)n);
    how = how*2 +1;
    int max = how/2;
    n-=max*max;
 
    ( n<=max ? n++ : n=how-n );
}
 
int main()
{
    int n = -1;
    while(std::cin >> n) 
    {
        find_in(n);
        std::cout << "\n :: " << n <<"\n";
    }
 
    system("pause");
    return(0);
}
с короткими поигрался, теперь можно длинные мастерить)

Добавлено через 6 минут
внесу поправочку
0
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
06.01.2018, 21:55 13
Цитата Сообщение от Maksat32 Посмотреть сообщение
C++
1
2
3
4
5
while(s<n){
    i++; 
    sb=s;
    s=s+i*2-1;
}
Сумма первых нечетных чисел это квадрат.
1 + 3 = 22
1 + 3 + 5 = 32
1 + ... + 2n - 1 = n2
Думаю в этой задаче надо это использовать. Правда с таких больших чисел корень извлекать самому нелегко... Потому часто олимпиадные задачи с длинной арифметикой пишутся на том языке где она доступна из коробки(Python / Java)
0
Диссидент
Эксперт C
26856 / 16758 / 3675
Регистрация: 24.12.2010
Сообщений: 37,521
06.01.2018, 22:11 14
Цитата Сообщение от Новичок Посмотреть сообщение
Думаю в этой задаче надо это использовать.
Я тоже так думаю. Но в этом топике так думаем только мы с вами. Может быть остальным это кажется непостижимой абракадаброй?
0
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
06.01.2018, 23:04 15
Байт, я думаю не так сложно это понять. ТС наверняка поймет. Вот только еще одна проблема остается: реализация длинной арифметики.
0
706 / 528 / 301
Регистрация: 24.02.2017
Сообщений: 1,881
06.01.2018, 23:51 16
Как сказано выше последовательность состоит из блоков. Каждый блок длинее на 2 единицы предыдущего. Вот и добрались до арефметической прогрессии. Сумма членов которой после преобразования будет выглядеть как S=n2. А так как
просят код, который будет работать хотя бы для N>1020 , то это будет выглядеть так n=1010*корень из S(где n число суммируеых членов). А это уже не длинная арифметика.
0
0 / 0 / 0
Регистрация: 06.01.2018
Сообщений: 13
07.01.2018, 00:21  [ТС] 17
Я написал код с учтенными выше комментариями:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream> 
#include <cmath> 
using namespace std; 
 
int main() 
{ 
 long long int ss,s,n,k; 
 cin»n; 
 if ((int(sqrt(n)))*(int(sqrt(n)))<n) k=int(sqrt(n))+1; else k=int(sqrt(n)); 
 s=k*k; 
 ss=2*k-1; 
 if (n-(s-ss)>k) cout«s-n+1«endl; else cout«n-(s-ss)«endl; 
 return 0; 
}
Но почему-то даже при числах, входящих в long long int выдает неправильный результат. Мне кажется, что ошибка в корне. Помогите мне ее исправить. Спасибо заранее.
0
Диссидент
Эксперт C
26856 / 16758 / 3675
Регистрация: 24.12.2010
Сообщений: 37,521
07.01.2018, 01:18 18
Maksat32, 1. Строка 9 вызывает буквально колики. Она плохо читаема. Функция sqrt достаточно затратна, чтобы стараться ее использовать как можно реже. Что помешало написать
C++
1
2
3
int r = (int)sqrt((double)n);
if (r*r<n) k=r+1; 
else k=r;
По основному вопросу трудно что-то сказать. Работа на пределе представления - чревата.
Попробуйте выводить промежуточные результаты. Иногда помогает.
0
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
07.01.2018, 01:20 19
Цитата Сообщение от Maksat32 Посмотреть сообщение
int(sqrt(n))
Сохранить в отдельную переменную. Использовать только long long. Лучше даже unsigned long long. И так как имя типа длинное я бы сделал как-то так, чтоб удобнее было
C++
1
using LL = unsigned long long; // можно назвать как угодно, я привык называть LL
0
Диссидент
Эксперт C
26856 / 16758 / 3675
Регистрация: 24.12.2010
Сообщений: 37,521
07.01.2018, 01:34 20
Цитата Сообщение от Новичок Посмотреть сообщение
Вот только еще одна проблема остается: реализация длинной арифметики.
Это да. Тут можно пойти путями разными. Взять готовую библиотеку - их мульен. Придумать свой велосипед (мульен+1). Оба этих пути имеют свои преимущества и недостатки. И выбор зависит от цели. Если хочешь поразмять мозги - конечно Второй. Критерий - быстрое написание кода? Тут бабушка надвое сказала. Иногда освоение чужой библиотеки становится дороже, чем написание собственной. Скорость? - тогда первый путь. Популярные библиотеки были сделаны серьезными людьми, и есть большая надежда, что и об оптимизации они подумали.

Добавлено через 3 минуты
Цитата Сообщение от Новичок Посмотреть сообщение
Сохранить в отдельную переменную.
Идеи просто носятся в воздухе
Цитата Сообщение от Новичок Посмотреть сообщение
Использовать только long long.
Да, это я пропустил
C++
1
LL r = (LL)sqrt((double)n);
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.01.2018, 01:34
Помогаю со студенческими работами здесь

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

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

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

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


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

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

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