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

Два указателя. Сложно - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ как выйти из циклов http://www.cyberforum.ru/cpp-beginners/thread859628.html
#include "stdafx.h" #include <stdio.h> #include <conio.h> #include <math.h> #include <Windows.h> #include <iostream> void main(void) { SetConsoleCP(1251);
C++ Почему так? Я вот уже довольно много времени читаю книги и разные коды по программированию, но все так и не понял. Почему хорошие программисты используют запись std:: а не просто в начале написать using namespace std; ?? В чем принципиальное различие между этими двумя записями и какую лучше применять? http://www.cyberforum.ru/cpp-beginners/thread859622.html
Необходимо написать калькулятор(деление), чтобы при выводе показывало 30 знаков после запятой C++
Необходимо написать калькулятор(деление), чтобы при выводе показывало 30 знаков после запятой. Типо 1/3 = 0,333333333333333333333333333334 P.S. Еще учитель просить использовать массив. Зачем? И как?
C++ поиск подстроки в строке
Всем доброго времени суток! Дано: две строки типа string, к примеру str1 = "HeLLo" и str2 = "hell" Вопрос: как найти из str1 подстроку str2 без учёта регистра? заранее спасибо
C++ Поиск и замена слов в файле txt http://www.cyberforum.ru/cpp-beginners/thread859590.html
Как заменить и найти слова в файле txt на С++. То есть есть файл вот такой структуры AAA БББ BBB 111 222 ыыы
C++ Рекурсивная функция Походу что-то с массивами не то, когда ввожу слишком большое число (15+), то выбивает ошибку с кучами\стеками, которую я не понимаю. using namespace std; void rekursija(long long factorials, int ArSize); int main() { cout << "Pls enter the number: " << endl; int ArSize; cin >> ArSize; long long * factorials = new long long; подробнее

Показать сообщение отдельно
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
11.05.2013, 00:27  [ТС]     Два указателя. Сложно
Цитата Сообщение от Toshkarik Посмотреть сообщение
a0 = X * b0 + Y = 1 * 6 + ( -2 )
b1 = (a * b0 + b) % c = (3 * 2 + 6) % 5 = 2
a1 = x * b1 + y = 1 * 2 + (-2) = 0
Вы не правильно поняли задание.
Последовательность нумеруется с единицы, но как вы храните, это не важно.
Но не в этом суть, а в том, что никто не может придумать алгоритм с двумя указателями, работающий за О(n), т.е. линейно (на этом форуме). У меня несколько знакомых первокуров её уже сдали.
Цитата Сообщение от Toshkarik Посмотреть сообщение
Плюс все находится в одном основном цикле, ну и проверка во вложенном цикле ( if ( i - j ) >= length ) позволяет избегать поиска когда уже есть вариант длины с бОльшим значением, чем осталось элементов для поиска.
А это на асимптотику не влияет, ваш алгоритм всё равно за О(n^2), как и мой, в моём есть ровно всё то, что вы сказали. Я уже проверял не пройдёт он.

Добавлено через 59 минут
Всё-таки спросил у друга, который сделал. Он помог. Тема закрыта. Вот код, работает он за О(n), жалко, конечно, что никто не помог, но всё равно спасибо
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
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std; 
 
#define ll long long
 
const int NMAX = 5000000;
 
ll from1toi[NMAX+1];
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n, x, y, a, b, c, s;
    cin >> n >> x >> y >> a >> b >> c >> s;
    ll curb = s;
    from1toi[0] = 0; 
    vector < pair<ll, ll> > mx, mn(1, make_pair(0,0));
    for (int i = 1; i <= n; i++){
        curb = (a * curb + b) % c;
        from1toi[i] = from1toi[i - 1] + x * curb + y;
        if (mn[mn.size() - 1].first > from1toi[i])
            mn.push_back(make_pair(from1toi[i], i));
    } 
    mx.push_back(make_pair(from1toi[n], n - 1));
    for(int i = n - 1; i >= 0; --i) {
        if(from1toi[i] > mx[mx.size() - 1].first)
            mx.push_back(make_pair(from1toi[i],i - 1));
    }
    int idx = 0, pos = 0, left = -1;
    for(int i = mn.size() - 1; i >= 0; i--) {
        while (pos < mx.size() && mx[pos].first < mn[i].first) {
            pos++;
        }
        if (mx[pos].second - mn[i].second > left || (mn[i].second < idx && mx[pos].second - mn[i].second == left)){
            idx = mn[i].second;
            left = mx[pos].second - mn[i].second;
        }
    }
    cout << idx + 1 << ' ' << left + 1 << endl;
    return 0;
}
 
Текущее время: 06:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru