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

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

06.08.2011, 01:53. Показов 10727. Ответов 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
Ответ Создать тему
Новые блоги и статьи
Был праздник вчера, а я и не знал.
kumehtar 28.07.2026
27. 07. 2026г. Intel Core 2 Duo исполнилось 20 лет Новости компьютерного мира и их обсуждение (4) Салют, шампанское, овации! :drink:
Нейтральные знания, чистый код - бла-бла-бла-бла, на самом деле кликбейт и самореклама, плагиат, и вот почему
Hrethgir 27.07.2026
То-есть отклонение такой публикации говорит само за себя, и пусть только возьмут на вооружение после отклонения публикации - это будет чистейшим актом плагиата. Отклонял Хабр. Дословно, отклонённая. . .
тв 16 бой ии
anaschu 27.07.2026
Великий Перелом ИИ: Как уравнения ОДУ Radau дожали цензурные фильтры Алисы Фиксируем в мемофонде Теории Всего беспрецедентный факт в истории ИИ-зондирования. В затяжном многораундовом. . .
мв 15. непроверенное, возможно, глюк
anaschu 27.07.2026
НАУЧНО-АНАЛИТИЧЕСКИЙ ОТЧЕТ. РАЗДЕЛ 1. 1: «НАУКА» (РАСШИРЕННАЯ СТЕХИОМЕТРИЧЕСКАЯ И ГЕНЕТИЧЕСКАЯ ВЕРСИЯ)Тема: Теоретическое обоснование инвариантности 19-мерного тензорного ядра непрерывных ОДУ и. . .
Очистка реквизитов и табличных частей документа при копировании (вариант 2)
Maks 26.07.2026
Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРаботу", разработанного в КА2. Задача: Заменить алгоритм запрета копирования документов для сотрудников с ролью "Стажер",. . .
Доктрина интенционального знания - Доктрина для портала "Срез".
Hrethgir 25.07.2026
Может найдётся кто захочет оценить доктрину. . . Написания правил участия для меня роскошь, требующая лимита времени, поэтому все сообщения не прошедшие модерацию будут видны только участникам портала,. . .
сукцессия 44. Решил подать на припринт в межународные сервисы препринтов. Но нужно одобрение от ученых
anaschu 25.07.2026
Английский вариант. Пока кто то не одобрит мою личность, мне не получиться это опубликовать на препринте. Но заявку на публикацию статьи я сегодня подам.
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил
anaschu 25.07.2026
две стороны одной монеты
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru