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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.96
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
06.08.2011, 01:53     Алгоритмы. Поиск верного решения задачи. #1
Крик души. Есть много замечательных книг по программированию, в них часто приводят стандартные алгоритмы. Переработал несколько из них:
Культин_С_С++_в задачах и примерах
Рацеев С.М. Язык Си. Структуры данных и алгоритмы
Седжвик Р. Фундаментальные алгоритмы на C++. (увы не вся.)

Но после прочтения, все равно огромные трудности с алгоритмической частью. Курс программирования дался очень тяжко. Подскажите в каком направлении двигаться, литературу честно говоря читать уже в без толку, когда не могу придумать как найти наибольшую цифру в числе. Конечно можно набрать кучу доп.задач, пробовать решать что то с форума.. Как говорил мой преподаватель: "я в программировании был полный ноль, пока не встретил одну книгу которая и научила программировать" - ведь программирование это не знание языка, а способность находить рациональные решения.
Расскажите, что вам помогло сложить это самое рациональное решение.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.08.2011, 01:53     Алгоритмы. Поиск верного решения задачи.
Посмотрите здесь:

C++ Две задачи, алгоритмы.
Разработать алгоритмы решения двух задач C++
C++ Алгоритм решения задачи
Задачи на циклические алгоритмы C++
Проблемы с алгоритмом решения задачи C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
08.08.2011, 13:50     Алгоритмы. Поиск верного решения задачи. #61
Цитата Сообщение от diagon Посмотреть сообщение
Ну как просто... Обычный перебор в 6 циклов имеет асимптотику O(10^6).
O(10^3) - перебор только первых трех чисел.
Кто вам сказал, что O(10^3) - это хорошее решение задачи?
Мой наихудший вариант имеет асимтотику О(10^2)...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 13:58     Алгоритмы. Поиск верного решения задачи. #62
diagon, Вы только тсс., все тихо делайте, а то Сыроежка Вас заставит итератор написать

Добавлено через 7 минут
А можно еще интереснее, выводить по увеличению веса, а все значения с одинаковым весом в лексикографическом порядке.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 13:58     Алгоритмы. Поиск верного решения задачи. #63
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Кто вам сказал, что O(10^3) - это хорошее решение задачи?
Мой наихудший вариант имеет асимтотику О(10^2)..
Наилучшее, которое я знаю, имеет асимптотику O(~140) =)
Но восходящую динамику сложнее найти, чем нисходящую.
По поводу вывода счастливых билетов в лексикографическом порядке - приходит в голову только забить все значения в int'овый массив, отсортировать его и вывести.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 14:01     Алгоритмы. Поиск верного решения задачи. #64
Цитата Сообщение от diagon Посмотреть сообщение
Наилучшее, которое я знаю, имеет асимптотику O(~140) =)
Но восходящую динамику сложнее найти, чем нисходящую.
По поводу вывода счастливых билетов в лексикографическом порядке - приходит в голову только забить все значения в int'овый массив, отсортировать его и вывести.
Ну, и кто Вам мешает похвастаться своим алгоритмом? Давайте.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 14:07     Алгоритмы. Поиск верного решения задачи. #65
Не совсем мой, видел на каком-то сайте...
Суть в том, что если найти сумму первых трех чисел, то всего счастливых билетов с такой суммой будет 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;
}
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 14:13     Алгоритмы. Поиск верного решения задачи. #66
[QUOTE=diagon;1896946]Не совсем мой, видел на каком-то сайте...
Суть в том, что если найти сумму первых трех чисел, то всего счастливых билетов с такой суммой будет sum^2.

Это очевидный комбинаторный факт. А знаете ли Вы, к примеру, что количество счастливых билетов, в общем случае, 2n-разрядных, это количество 2n-разрядных чисел с суммой цифр 3^n, поэтому и говорю, что на бумаге легко считается
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
08.08.2011, 14:13     Алгоритмы. Поиск верного решения задачи. #67
Цитата Сообщение от diagon Посмотреть сообщение
Наилучшее, которое я знаю, имеет асимптотику O(~140) =)
Но восходящую динамику сложнее найти, чем нисходящую.
По поводу вывода счастливых билетов в лексикографическом порядке - приходит в голову только забить все значения в int'овый массив, отсортировать его и вывести.
Рассмотрите такой подход: для числа 1-9 найти все разбиения на 3 слагаемых. Можно даже от 2 до 9, так как для 1 разбиение тривиально.
И выводить можно, не используя массив. Если генерировать разложение в порядке возрастания.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 14:22     Алгоритмы. Поиск верного решения задачи. #68
Цитата Сообщение от diagon Посмотреть сообщение
По поводу вывода счастливых билетов в лексикографическом порядке - приходит в голову только забить все значения в int'овый массив, отсортировать его и вывести.
Да, и по поводу сортировки, надеюсь Вы не массив sum говорили
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 14:30     Алгоритмы. Поиск верного решения задачи. #69
Ну и за 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?
Долговато как-то =)
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
08.08.2011, 14:33     Алгоритмы. Поиск верного решения задачи. #70
diagon, да, конечно, до 27, причем слагаемые от 0 до 9.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 14:55     Алгоритмы. Поиск верного решения задачи. #71
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;
}
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
08.08.2011, 15:03  [ТС]     Алгоритмы. Поиск верного решения задачи. #72
Как бурно развивается тема)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 15:06     Алгоритмы. Поиск верного решения задачи. #73
Хм... Интересно...
Только зачем массив обнулять, я ведь его в глобальную область специально для этого и засунул =)
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 15:17     Алгоритмы. Поиск верного решения задачи. #74
Цитата Сообщение от diagon Посмотреть сообщение
Хм... Интересно...
Только зачем массив обнулять, я ведь его в глобальную область специально для этого и засунул =)
Это привычка, редко глобальными переменными пользуюсь, разве же это так важно, соль то вся в алгоритме
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 20:42     Алгоритмы. Поиск верного решения задачи. #75
Нашел еще одну задачку с очень красивым решением =)
Дано n (0 < n <= 50) строк длиной не более 1000 символов, в которых записаны двоичные представления чисел. Для каждого из этих чисел определить, делятся ли они в десятичной системе счисления на 7.
P.S. переводить в десятичную систему счисления бесполезно - числа просто не влезут в целочисленные типы и придется писать длинку, которая не пройдет по времени(ограничение - 1 секунда). Есть гораздо более изящное решение =)
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
10.08.2011, 20:48     Алгоритмы. Поиск верного решения задачи. #76
дай ссылку на задачу)
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
10.08.2011, 20:50     Алгоритмы. Поиск верного решения задачи. #77
diagon, надо поиграться с битовым представлением. тут регулярность появления последовательностей нулей и единиц должна проявляться...
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 20:52     Алгоритмы. Поиск верного решения задачи. #78
Цитата Сообщение от Maxwe11 Посмотреть сообщение
дай ссылку на задачу)
Там разбор есть. Не дам =)

Цитата Сообщение от ValeryLaptev Посмотреть сообщение
diagon, надо поиграться с битовым представлением. тут регулярность появления последовательностей нулей и единиц должна проявляться...
Не совсем... Играться нужно с системами счисления.
ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
10.08.2011, 20:56     Алгоритмы. Поиск верного решения задачи. #79
diagon, ну, эт понятно - восьмеричная система счисления. По три бита сворачиваем.
Но и в двоичной - есть там регулярность битов...
Ага! Если система семиричная, то в конце должны быть нули...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2011, 21:02     Алгоритмы. Поиск верного решения задачи.
Еще ссылки по теме:

C++ Разработать алгоритмы и программы решения задач
Нужны задачи для их решения C++
C++ не знаю решения задачи в c ++

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2011, 21:02     Алгоритмы. Поиск верного решения задачи. #80
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
Ага! Если система семиричная, то в конце должны быть нули...
Переводить больно сложно. Ну и это доказать еще нужно...

Решение + ссылка.
Цитата Сообщение от ValeryLaptev Посмотреть сообщение
восьмеричная система счисления. По три бита сворачиваем.
Это было правильным. В десятичной системе счисления число делится на 9, если сумма его цифр делится на 9. В восьмеричной системе счисления число делится на 7, если сумма его цифр делится на 7 =) Итого просто переводим число в восьмеричную систему счисления и находим сумму его цифр.
Ссылка на задачу(там более подробный разбор).
Yandex
Объявления
10.08.2011, 21:02     Алгоритмы. Поиск верного решения задачи.
Ответ Создать тему
Опции темы

Текущее время: 04:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru