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

Нужно сделать алгоритм, решающий задачу за время н - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Работа с текстовыми файлами в С++ http://www.cyberforum.ru/cpp-beginners/thread645322.html
Здравствуйте. На лето задали написать прогу в среде visual studio c++, но этот предмет у меня закончился зимой и я конечно уже забыл значительную часть этого языка. Поиск в интернете ничего более менее полезного пока не дал и я хотел попросить помочь вас с парочкой вопросов. Само задание: "В программе создать текстовый файл и записать в него строки, вводимые с клавиатуры до тех пор, пока не...
C++ исправление ошибок //funkcijas1 #include <iostream> using namespace std; int main() { int i, fact=1, n; cout <<"Введите целое число в диапазоне от 1 до 12!" << endl; cin>>n; for (i=1; i<=n; i++) http://www.cyberforum.ru/cpp-beginners/thread645316.html
C++ Поток с GetMessage
Привет всем. У меня в программе в отдельном потоке имеется такой код: while(GetMessage(&msg,0,0,0) { TranslateMessage(&msg); DispatchMessage(&msg); } Из основной программы я запускаю этот поток и программа останавливается на нём, хотя она должна продолжить выполняться дальше. В чем моя ошибка?
Значение переменных C++
Для Х, принимающего значения от XN до XK с шагом ∆X, определить Y. При условии: Значения всех переменных определить по таблице 1. Результат выдать в форме таблицы значений X иY. Для таблицы обеспечить подпись столбцов. N 0 1 2 3 4 5 6 7 8 9 A √9-x Ln 6x (x-4)^2 Log5x √x e^x-8.6 Log3x e^2x+0.2 Log2x √x+2 B Log4x 5x Tg1/2x Sin3x Log2x Sin x x-32 Log7x 12 Log3x C -10 ...
C++ если ли стандартное исключение чтоб перехватывало http://www.cyberforum.ru/cpp-beginners/thread645200.html
что б перехватывало а ля unsigned int a = - 2 ; try { cout << a ; }
C++ без знаковый double. Если ли чтоб можно было в шаблон пихать или самому сделать придется ? сабжж подробнее

Показать сообщение отдельно
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35

Нужно сделать алгоритм, решающий задачу за время н - C++

01.09.2012, 13:45. Просмотров 435. Ответов 4
Метки (Все метки)

Всем привет!
Есть задача:
Исходные данные
В первой строке записано целое число N — количество бильярдных шаров (1 ≤ N ≤ 100000). В следующих N строках даны номера этих шаров в том порядке, в котором ревизор забирал их из лузы.
Результат
Выведите слово «Cheater», если закатывающий не мог закатить все N шаров в правильном порядке. Иначе выведите «Not a proof».

Реализовывал несколько алгоритмов. Первый работал за время O(n), но не всегда решал правильно. Второй алгоритм решает правильно, но за время O(n^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
#include "stdafx.h"
#include <stdio.h>
bool SearchInViewed(int begin, int end, int *view, int j)
{
    if (begin - end > 10)
        end = begin - 10;
    for (int i = begin - 1; i > end; i--)
    {
        if (view[i] == 0)
            return false;
    }
    return true;
}
 
int main()
{
    int n, _prev;
    bool result = true;
    int viewed[100001] = {0};
    scanf("%d",&n);
    int number;
    scanf("%d", &number);
    _prev = number;
    for (int i = 0; i < n-1; i++)
    {
        scanf("%d", &number);
        if (result)
        {
            if ((_prev - number) > 1)
            {
                if (!SearchInViewed(_prev, number, viewed))
                {
                    result = false;
                }
            }
            viewed[_prev]++;
            _prev = number;
        }
    }
    (result) ? (printf("Not a proof\n")) : (printf("Cheater\n"));
    return 0;
}
Я конечно сократил время его выполнения, сделав условие в ф-ции
C++
1
2
    if (begin - end > 10)
        end = begin - 10;
Но такое условие неправильно. Т.к. тогда могут возникнуть ситуации, когда алгоритм неправильно решает.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 09:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru