Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перегрузка оператора в шаблонном классе Здравствуйте! Есть шаблонный класс Array, описывающий массив. Такая проблема: нужно перегрузить оператор "<", который сравнивает длины двух массивов и возвращает true, если первый меньше, но при этом, если создается массив типа char, сравнение должно работать лексикографически(то есть используя функцию strcmp). Как прописать эту перегрузку? template <class M> class Array { int len; ... https://www.cyberforum.ru/ cpp-beginners/ thread2228580.html C++ Добавление нулевого элемента в линейный список
Здравствуйте! Подскажите пожалуйста как реализовать добавление нулевого элемента в линейный список. Иными словами - необходимо записать новый элемент перед первым в очереди. Пытался - не выходит корректная перестановка элементов. За вид кода - прошу прощения.Он был получен путем копипасты. Среда разработки Dev-C++ #include <fstream> #include <iostream> #include <cstdlib> #include <ctime>...
C++ Нахождение потока в графе Нужна помощь в нахождение потока в графе. Например есть построенный граф на 5 вершин и подобие программы которая жалуется на . И вот сама программа #include "stdio.h" #include <iostream> #include <fstream> #include <Windows.h> #include <time.h> #include <vector> #include "conio.h" #include <math.h> https://www.cyberforum.ru/ cpp-beginners/ thread2228548.html C++ Решения нелинейных уравнений (проверка) https://www.cyberforum.ru/ cpp-beginners/ thread2228505.html
Вообщем код у меня почти готов, но мне нужно еще сделать проверку уравнения с уже полученным ответом, а до меня что-то не доходит как это сделать. Буду очень благодарен за помощь. И еще, если будет не трудно, можете проверить правильный ли получился ответ (просто что-то меня смущает ответ -1, без каких либо соты или тысячных, слишком он простой для ответа нелинейного уравнения) (само уравнение:...
Неуспевающие студенты C++
Создать класс, содержащий сведения о сдаче студентами сессии. Класс должен содержать следующие данные: индекс группы, фамилия студента, оценки по четырем экзаменам, и оценки по пяти зачетам. написать программу, выдающую фамилии неуспевающих студентов с указанием индексов групп и количеством задолженностей, средний балл, полученный каждым студентом группы Х и всей группой в целом. Данные и...
C++ Переделать программу без использования библиотеки <vector> Доброго времени. Программа не моя, но немного переделанная, нашел её здесь. Хотелось бы её увидеть без использования векторов. Спасибо! #include <cmath> #include <iomanip> #include <vector> #include <string> #include <iostream> https://www.cyberforum.ru/ cpp-beginners/ thread2228500.html
C++ Использование функций пользователя при работе с массивами Нужно написать програму на С++ для вычисления значения F с использованиям функций пользователя вычисления елементов массиву x . Вот само задание Функция | Процедура F = \prod_{i=1}^{N}{x}_{i}+a\sum_{i=1}^{n}{x}_{i}|{x}_{i}=a\sum_{j=1}^{m}sin{b}_{ij}+c Количество строк n|Количество столбцов m|Начальный номер строки|Начальный номер столбца 3|10|1|1 const a = 0.98, c = 1.1 https://www.cyberforum.ru/ cpp-beginners/ thread2228476.html C++ Найти максимальный отрицательный элемент массива
Дан одномерный массив, состоящий из N целых элементов. Введите массив с клавиатуры; Найдите максимальный отрицательный элемент массива; Вычислите сумму отрицательных элементов массива; Выведите положительные элементы на экран. П.5.16.Правил Запрещено создавать темы с множеством вопросов во всех разделах, кроме разделов платных услуг. Один вопрос - одна тема. Помогите пожалуйста найти и...
C++ Незадача с паттерном Цепочка обязанностей https://www.cyberforum.ru/ cpp-beginners/ thread2228431.html
В общем задание такое. Реализовать сказку(колобок). Естественно не через cout . И с обязательным применением цепочки обязанности. У меня есть пока что 4 класса. Они еще не связаны между собой, так как сначала нужно решить проблему о которой я рассказываю. Короче, у меня есть файл, в котором текст сказки. И есть файл с командами. Исходя из команд, выполняются те или иные методы. Пока что проблема...
C++ Вывод односвязного списка Здравствуйте. Столкнулся с такой задачей. Нужно инициализировать односвязный список, ввести его с клавиатуры и вывести. Перепробовал все способы. Но почему-то при выводе списка выводится только первый элемент. Может кто знает как исправить? Заранее благодарю P.S. Данные в списке представлены в виде структуры. И заранее не известно сколько пользователь введет элементов списка #include... https://www.cyberforum.ru/ cpp-beginners/ thread2228426.html
Ошибка в алгоритме проверки строки C++
Проверяю строку на корректность, все работает нормально, кроме одной вещи. Сделал алгоритм для удаления лишних пробелов. Если введенная строка имеет 20 или меньше символов - все нормально работает. Если она больше 20 - строка в конце заполняется разными непонятными символами. void control_name_car() { int i, j, dl1, kol_s, n; char second_str; cout << endl << endl; metka_car: ...
13 / 13 / 9
Регистрация: 28.07.2017
Сообщений: 103
0

Подсчеты в строю - оптимальный алгоритм - C++ - Ответ 12305684

13.04.2018, 23:03. Показов 1412. Ответов 1
Метки (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте. Есть задача. Условие следующее:

Кликните здесь для просмотра всего текста

Так, например, если в шеренге стоят 4 солдата ростом https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{1} = 178, https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{2} = 180, https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{3} = 170, https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{4} =

190, а также все солдаты смотрят влево, то 2-й солдат будет видеть только 1-го, 3-й — только 2-го (так как между ним и первым есть более высокий второй солдат), 4-й будет

видеть 2-го и 3-го солдат.
Так как делать в строю все равно больше нечего, Вася хочет посчитать, сколько человек видит
каждый из солдат.

Формат входных данных:
Первая строка входных данных содержит число n — количество солдат в шеренге (1 https://www.cyberforum.ru/cgi-bin/latex.cgi?{\ll }_{} n https://www.cyberforum.ru/cgi-bin/latex.cgi?{\ll }_{} https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{5}).

Вторая строка содержит n чисел https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{1}, https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{2},..., https://www.cyberforum.ru/cgi-bin/latex.cgi?{h}_{n} — рост солдат в шеренге (1 https://www.cyberforum.ru/cgi-bin/latex.cgi?{\ll }_{} n https://www.cyberforum.ru/cgi-bin/latex.cgi?{\ll <br />
<br />
}_{} https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{5}).

Третья строка содержит n символов, описывающих направление, в которые смотрят солдаты:
i-й символ равен «L», если i-й солдат смотрит влево, то есть потенциально может увидеть только солдат с номерами 1, 2,..., i - 1, либо «R», если i-й солдат смотрит вправо и потенциально может увидеть только солдат с номерами i + 1, i + 2,..., n.

Формат выходных данных:
Выведите n целых чисел, i-е из выведенных чисел должно быть равно числу солдат, которых видит i-й солдат в строю.


Пример:
Кликните здесь для просмотра всего текста

Ввод:
4
178 180 170 190
LLLL
Вывод:
0 1 1 2

Ввод:
5
178 180 175 170 190
LLRLL
Вывод:
0 1 2 2 3

Ввод:
5
178 180 170 170 160
LLRLL
Вывод:
0 1 1 2 3


Алгоритм полным перебором слишком долгий. По веремени он не проходит.
Вот его реализация:
Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <cstdio>
#include <string>
 
void fill_all (int *arr, const int &qSolders, std::string &str)
{
    for (int ind = 0; ind < qSolders; ++ind)
    {
        scanf ("%d", &arr[ind]);
    }
    std::cin >> str;
}
 
void calc (int *arr, const int &qSolders, const std::string &str)
{
    for (int ind = 0; ind < qSolders; ++ind)
    {
        int counter = 0;
        if (str[ind] == 'L')
        {
            int bH = 0;
            for (int subInd = ind - 1; subInd >= 0; --subInd)
            {
                if (arr[subInd] >= bH)
                {
                    ++counter;
                    bH = arr[subInd];
                }
            }
        }
        else
        {
            int bH = 0;
            for (int subInd = ind + 1; subInd < qSolders; ++subInd)
            {
                if (arr[subInd] >= bH)
                {
                    ++counter;
                    bH = arr[subInd];
                }
            }
        }
        printf ("%d ", counter);
    }
    printf ("\n");
}
 
int main ()
{
    int qSolders;
    std::cin >> qSolders;
 
    int *arr = new int [qSolders];
    std::string str;
    fill_all (arr, qSolders, str);
    calc (arr, qSolders, str);
 
    return 0;
}


Потом я попытался улучшить алгоритм, но не получилось, поскольку, время то и улучшилось (я думаю), но работает он неправильно.
Вот его реализация:
Кликните здесь для просмотра всего текста

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
#include <iostream>
#include <cstdio>
#include <string>
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void fill_all (int *arr, int *ans, const int &qSolders, std::string &str);
void calc (int *arr, int *ans, const int &qSolders, const std::string &str);
void cycle (int *arr, int *ans, const std::string &str, const int &qSolders, int &index, const int &ind, int &bh, char ch);
void printOut (int *ans, const int &size);
template <typename T> T abs (T num);
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main ()
{
    int qSolders;
    std::cin >> qSolders;
 
    int *arr = new int [qSolders];
    int *ans = new int [qSolders];
    std::string str;
    fill_all (arr, ans, qSolders, str);
    calc (arr, ans, qSolders, str);
    printOut (ans, qSolders);
 
    return 0;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void fill_all (int *arr, int *ans, const int &qSolders, std::string &str)
{
    for (int ind = 0; ind < qSolders; ++ind)
    {
        scanf ("%d", &arr[ind]);
        ans[ind] = 0;
    }
    std::cin >> str;
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void calc (int *arr, int *ans, const int &qSolders, const std::string &str)
{
    //////////////////////////////////
    ///Left
    int bh = 0;
    int index = 0;
    for (int ind = 0; ind < qSolders; ++ind)
    {
        cycle (arr, ans, str, qSolders, index, ind, bh, 'R');
    }
 
    //////////////////////////////////
    ///Right
    bh = 0;
    index = qSolders - 1;
    for (int ind = qSolders - 1; ind >= 0; --ind)
    {
        cycle (arr, ans, str, qSolders, index, ind, bh, 'L');
    }
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void cycle (int *arr, int *ans, const std::string &str, const int &qSolders, int &index, const int &ind, int &bh, char ch)
{
    //////////////////////////////////
    if (str[ind] != ch)
    {
        ans[ind] = abs(ind - index);
    }
 
    //////////////////////////////////
    if (arr[ind] >= bh)
    {
        bh = arr[ind];
        index = ind;
    }
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void printOut (int *ans, const int &size)
{
    for (int ind = 0; ind < size; ++ind)
    {
        printf ("%d ", ans[ind]);
    }
    printf ("\n");
}
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
template <typename T>
T abs (T num)
{
    return num < 0 ? -num : num;
}


При таком алгоритме ход "мышления" такой: сначала преребираем всех солдат, которые смотрят в одну сторону, затем, в другую.
Перебирая каждую сторону мы запоминаем индекс самого большого солдата (т.е. того, после которого мы ничего не сможем увидеть).
Например, у нас есть солдаты в таком порядке 1 2 3 4 99 98 97.
Солдат номер 1, смотрящий направо будет видеть всех солдат до тех пор, пока не увидит солдата с высотой 99.

И вот тут, если немного изменить порядок, алгоритм уже работает неправильно. К примеру, на такой: 1 2 4 3 99 98 97.
Алгоритм вычислит тот же ответ, что и в предыдущем примере, однако солдат 1 не сможет увидеть солдата с высотой 3, т.к. предыдущий солдат выше, чем 3.

Подскажите, пожалуйста, каким образом можно решить данную задачу.
Заранее, спассибо (:

Вернуться к обсуждению:
Подсчеты в строю - оптимальный алгоритм C++
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.04.2018, 23:03
Готовые ответы и решения:

оптимальный алгоритм
найти сумму простых чисел от 1 до A program kl; var s,m,p,n,A:integer; begin read (A); for...

Оптимальный алгоритм сортировки
Камрады! Есть функция/процедура f(m,n), которая получает 2 номера и возвращает n,m (n&gt;m) т.е....

Оптимальный алгоритм сортировки
Доброго времени суток! Есть некий класс: public class Person { public string Name {...

Оптимальный алгоритм амплитудного демодулятора
Доброго времени суток. Возникла задача - детектирование АМ сигнала с синусоидальной несущей в 4...

1
13.04.2018, 23:03
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.04.2018, 23:03
Помогаю со студенческими работами здесь

Перемножение матриц. Оптимальный алгоритм
Доброе время суток! Объясните пожалуйста почему такой алгоритм перемножения матриц: for (int i...

Оптимальный алгоритм рисования линий
1) Является ли алгоритм рисования линии перебором точек оптимальным? for(float i=Xmin, j; i&lt;=Xmax;...

Перебор цифр и оптимальный алгоритм
Всем, добрый день. Есть набор цифр от 1 до 5. В числе может быть от 1 до 15 цифр. Например,...

Помогите написать оптимальный алгоритм по рисунку
Нужна ваша помощь, помогите написать оптимальный алгоритм по рисунку. Это мой код: uses ...

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