Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.77/48: Рейтинг темы: голосов - 48, средняя оценка - 4.77
заставил Бендера
 Аватар для IIIa66uMEM6eP
854 / 319 / 17
Регистрация: 05.12.2010
Сообщений: 1,707
Записей в блоге: 6

Алгоритмы. Поиск верного решения задачи.

06.08.2011, 01:53. Показов 11385. Ответов 79
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Крик души. Есть много замечательных книг по программированию, в них часто приводят стандартные алгоритмы. Переработал несколько из них:
Культин_С_С++_в задачах и примерах
Рацеев С.М. Язык Си. Структуры данных и алгоритмы
Седжвик Р. Фундаментальные алгоритмы на C++. (увы не вся.)

Но после прочтения, все равно огромные трудности с алгоритмической частью. Курс программирования дался очень тяжко. Подскажите в каком направлении двигаться, литературу честно говоря читать уже в без толку, когда не могу придумать как найти наибольшую цифру в числе. Конечно можно набрать кучу доп.задач, пробовать решать что то с форума.. Как говорил мой преподаватель: "я в программировании был полный ноль, пока не встретил одну книгу которая и научила программировать" - ведь программирование это не знание языка, а способность находить рациональные решения.
Расскажите, что вам помогло сложить это самое рациональное решение.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
06.08.2011, 01:53
Ответы с готовыми решениями:

Алгоритмы для решения
Через какие алгоритмы можно реализовать эти две задачи.

Написать программу решения системы тригонометрических уравнений (разветвляющиеся алгоритмы)
Здравствуйте уважаемые форумчане, требуется ваша помощь. Я немного затрудняюсь в написании кода разветвляющихся алгоритмов, очень прошу...

Задачи на циклические алгоритмы
Помогите пожалуйста сделать в с++: 1)Написать функцию, которая по целому a вычисляет и возвращает максимальное n, при котором n! ≤...

79
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
08.08.2011, 13:50
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от diagon Посмотреть сообщение
Ну как просто... Обычный перебор в 6 циклов имеет асимптотику O(10^6).
O(10^3) - перебор только первых трех чисел.
Кто вам сказал, что O(10^3) - это хорошее решение задачи?
Мой наихудший вариант имеет асимтотику О(10^2)...
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
08.08.2011, 13:58
diagon, Вы только тсс., все тихо делайте, а то Сыроежка Вас заставит итератор написать

Добавлено через 7 минут
А можно еще интереснее, выводить по увеличению веса, а все значения с одинаковым весом в лексикографическом порядке.
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 13:58
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Кто вам сказал, что O(10^3) - это хорошее решение задачи?
Мой наихудший вариант имеет асимтотику О(10^2)..
Наилучшее, которое я знаю, имеет асимптотику O(~140) =)
Но восходящую динамику сложнее найти, чем нисходящую.
По поводу вывода счастливых билетов в лексикографическом порядке - приходит в голову только забить все значения в int'овый массив, отсортировать его и вывести.
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
08.08.2011, 14:01
Цитата Сообщение от diagon Посмотреть сообщение
Наилучшее, которое я знаю, имеет асимптотику O(~140) =)
Но восходящую динамику сложнее найти, чем нисходящую.
По поводу вывода счастливых билетов в лексикографическом порядке - приходит в голову только забить все значения в int'овый массив, отсортировать его и вывести.
Ну, и кто Вам мешает похвастаться своим алгоритмом? Давайте.
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 14:07
Не совсем мой, видел на каком-то сайте...
Суть в том, что если найти сумму первых трех чисел, то всего счастливых билетов с такой суммой будет sum^2.
Ну и как-то так получится.
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
int sum[28];
int main(){
    for (int a = 0; a <= 9; ++a)
        for (int b = 0; b <= 9; ++b)
            for (int c = 0; c <= 9; ++c)
                ++sum[a + b + c];
    unsigned count = 0;
    for (int i = 0; i < 28; ++i)
        count += sum[i] * sum[i];
    std::cout << count;
}
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
08.08.2011, 14:13
[QUOTE=diagon;1896946]Не совсем мой, видел на каком-то сайте...
Суть в том, что если найти сумму первых трех чисел, то всего счастливых билетов с такой суммой будет sum^2.

Это очевидный комбинаторный факт. А знаете ли Вы, к примеру, что количество счастливых билетов, в общем случае, 2n-разрядных, это количество 2n-разрядных чисел с суммой цифр 3^n, поэтому и говорю, что на бумаге легко считается
0
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
08.08.2011, 14:13
Цитата Сообщение от diagon Посмотреть сообщение
Наилучшее, которое я знаю, имеет асимптотику O(~140) =)
Но восходящую динамику сложнее найти, чем нисходящую.
По поводу вывода счастливых билетов в лексикографическом порядке - приходит в голову только забить все значения в int'овый массив, отсортировать его и вывести.
Рассмотрите такой подход: для числа 1-9 найти все разбиения на 3 слагаемых. Можно даже от 2 до 9, так как для 1 разбиение тривиально.
И выводить можно, не используя массив. Если генерировать разложение в порядке возрастания.
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
08.08.2011, 14:22
Цитата Сообщение от diagon Посмотреть сообщение
По поводу вывода счастливых билетов в лексикографическом порядке - приходит в голову только забить все значения в int'овый массив, отсортировать его и вывести.
Да, и по поводу сортировки, надеюсь Вы не массив sum говорили
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 14:30
Ну и за O(~140) едва вспомнил =)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
int main(){
    unsigned count = 0;
    for (int sum = 0; sum <= 13; ++sum)
    {
        int tmp = 0;
        for (int x = std::max(0, sum - 18); x <= std::min(9, sum); ++x)
            tmp = tmp + std::min(9, sum - x) - std::max(0, sum - x - 9) + 1;
        count += tmp * tmp;
    }
    count *= 2;
    std::cout << count;
}
Тут перебор идет уже по сумме и определяется, какое количество комбинаций первых трех цифр ее имеет.

Цитата Сообщение от Olga_ Посмотреть сообщение
Да, и по поводу сортировки, надеюсь Вы не массив sum говорили
Нет, он только для сохранения результата нужен.

Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Рассмотрите такой подход: для числа 1-9 найти все разбиения на 3 слагаемых. Можно даже от 2 до 9, так как для 1 разбиение тривиально.
И выводить можно, не используя массив. Если генерировать разложение в порядке возрастания.
Не совсем понятно.. Если 0-27 разбивать на 3 слагаемых, то в общем-то можно.
то очевидный комбинаторный факт. А знаете ли Вы, к примеру, что количество счастливых билетов, в общем случае, 2n-разрядных, это количество 2n-разрядных чисел с суммой цифр 3^n, поэтому и говорю, что на бумаге легко считается
Эээ... Каким образом считается?
Просто перебираются все числа с суммой цифр 3^n?
Долговато как-то =)
0
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
08.08.2011, 14:33
diagon, да, конечно, до 27, причем слагаемые от 0 до 9.
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
08.08.2011, 14:55
Diagon, Ваш прежний алгоритм из O(n^3) легко преобразуется в O(120)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
int sum[28] = {0};
int main()
{
        for (int a = 0; a <= 9; ++a)
        {
                for (int b = 0; b < a; ++b)
                {
                        for (int c = 0; c < b; ++c)
                        {
                             sum[a + b + c] += 6;
                        }
                        sum[2*a + b] += 3;
                        sum[a + 2*b] += 3;
                }
                ++sum[3*a];
        }
        unsigned count = 0;
        for (int i = 0; i < 28; ++i)
                count += sum[i] * sum[i];
        std::cout << count;
        return 0;
}
2
заставил Бендера
 Аватар для IIIa66uMEM6eP
854 / 319 / 17
Регистрация: 05.12.2010
Сообщений: 1,707
Записей в блоге: 6
08.08.2011, 15:03  [ТС]
Как бурно развивается тема)
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 15:06
Хм... Интересно...
Только зачем массив обнулять, я ведь его в глобальную область специально для этого и засунул =)
0
 Аватар для Olga_
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
08.08.2011, 15:17
Цитата Сообщение от diagon Посмотреть сообщение
Хм... Интересно...
Только зачем массив обнулять, я ведь его в глобальную область специально для этого и засунул =)
Это привычка, редко глобальными переменными пользуюсь, разве же это так важно, соль то вся в алгоритме
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 20:42
Нашел еще одну задачку с очень красивым решением =)
Дано n (0 < n <= 50) строк длиной не более 1000 символов, в которых записаны двоичные представления чисел. Для каждого из этих чисел определить, делятся ли они в десятичной системе счисления на 7.
P.S. переводить в десятичную систему счисления бесполезно - числа просто не влезут в целочисленные типы и придется писать длинку, которая не пройдет по времени(ограничение - 1 секунда). Есть гораздо более изящное решение =)
0
Каратель
Эксперт С++
6610 / 4029 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
10.08.2011, 20:48
дай ссылку на задачу)
0
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
10.08.2011, 20:50
diagon, надо поиграться с битовым представлением. тут регулярность появления последовательностей нулей и единиц должна проявляться...
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 20:52
Цитата Сообщение от Maxwe11 Посмотреть сообщение
дай ссылку на задачу)
Там разбор есть. Не дам =)

Цитата Сообщение от ValeryLaptev Посмотреть сообщение
diagon, надо поиграться с битовым представлением. тут регулярность появления последовательностей нулей и единиц должна проявляться...
Не совсем... Играться нужно с системами счисления.
0
Эксперт С++
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
10.08.2011, 20:56
diagon, ну, эт понятно - восьмеричная система счисления. По три бита сворачиваем.
Но и в двоичной - есть там регулярность битов...
Ага! Если система семиричная, то в конце должны быть нули...
0
Higher
 Аватар для diagon
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 21:02
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Ага! Если система семиричная, то в конце должны быть нули...
Переводить больно сложно. Ну и это доказать еще нужно...

Решение + ссылка.
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
восьмеричная система счисления. По три бита сворачиваем.
Это было правильным. В десятичной системе счисления число делится на 9, если сумма его цифр делится на 9. В восьмеричной системе счисления число делится на 7, если сумма его цифр делится на 7 =) Итого просто переводим число в восьмеричную систему счисления и находим сумму его цифр.
Ссылка на задачу(там более подробный разбор).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
10.08.2011, 21:02

Инкапсуляция. Поиск верного решения
Добрый вечер! Вот такая программка, почему здесь &quot;d.name&quot; отображается красным и пишется что &quot;String name&quot; private. Ну там я же...

Определить тип задачи и указать возможные алгоритмы решения
В общем, решение задачи НЕ ТРЕБУЕТСЯ, необходимо определить её тип и указать возможные алгоритмы решения к данной задачи. Впервые...

Нет верного решения при определенном значении параметра
Добрый день. Стоит задача получить значения переменной x или лямбда из уравнения и доп. условия при значениях косинуса фи от 0 до 1. ...

Поиск решения задачи в Excel
Помогите решить задачу...буду очень благодарен &quot;Рассчитать, какая сумма окажется на счете, если 40 т. руб. положены на 22 года под 12%...

Поиск архитектурного решения для поставленной задачи
Доброго времени суток всем. Нужен совет - как построить структуру работы приложения для моей текущей задачи. (не пинайте ногами -...


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

Или воспользуйтесь поиском по форуму:
80
Ответ Создать тему
Новые блоги и статьи
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта
8Observer8 08.11.2026
Содержание блога | English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle | Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят
zorxor 08.11.2026
Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ.
zorxor 08.11.2026
Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL
8Observer8 07.11.2026
Содержание блога | English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике
Maks 07.11.2026
Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru