Вернуться   Развлекательный портал CN.ru - Форум > Технологии > Программирование > Начинающим

Ответ
 
Опции темы
Старый 29.11.2012, 15:57 ↑ #1
IIocJIeCMepTu Мужской
завсегдатай эго-форума
 
Аватар для IIocJIeCMepTu
 
Регистрация: 09.07.2008
Адрес: Новосибирск и разные уголки России
Возраст: 33
Сообщений: 291
Репутация: 2116
IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг IIocJIeCMepTu мегамозг
По умолчанию Верните сон!!!

В общем изучаю потихоньку С++
Было задание с помощью вложенных циклов for прямым подбором найти тройки Пифогора (стороны прямоугольного треугольника)
Написал програмку
Код:
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int n;
    cout << "Vvedite granicu poiska: \n";
    cin >> n;

    cout << endl << "Troiki pifagora do " << n << endl;

    cout << "katet 1" << setw(15) << "katet 2" << setw(15) << "gipatenuza" << endl;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
                {
                    if(i * i + j * j == k * k)
                        cout << i << setw(15) << j << setw(15) << k << endl;
                }

    return 0;
}
В программке чуть оптимизировал код циклов. Т.к. прямым подбором, при n=100 и их будет 100*100*100 = 1000000.

Код:
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int n;
    cout << "Vvedite granicu poiska: \n";
    cin >> n;

    cout << endl << "Troiki pifagora do " << n << endl;

    cout << "katet 1" << setw(15) << "katet 2" << setw(15) << "gipatenuza" << endl;

    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            for(int k = j; k <  i + j && k <= n; k++)
                {
                    if(i * i + j * j == k * k)
                        cout << i << setw(15) << j << setw(15) << k << endl;
                }

    return 0;
}
Убрал лишние циклы, где пара катетов будет дублироваться (напр 23 46 и 46 23), где гипатенуза будет меньше большего из катетов и где она будет больше их суммы (таких треугольнив существовать не может). Ввел в код каунтер (подсчет общего количество циклов). 87 тыс получилось. Что в 11.5 раз лучше прямого подбора без оптимизации.
И тут столкнулся с вопросом. Как посчитать это аналитически. Пока считал, ушел в дебри комбинаторики. Считал количество сочетаний, потом додумался, что считать надо размещения, т.к. для подсчета количества циклов важна последовательность чисел. В первом случае это n^k (100^3) = 1000000.
Как посчитать второй случай? Ведь там 2ой элемент зависит от 1го (не меньше, чем, чтобы исключить повторения пар катетов), 3ий элемент зависит от первых 2ух (не меньше любого из них и меньше их суммы).
Голову уже изломал. Забыл комбинаторику.
IIocJIeCMepTu вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Текущее время: 01:58. Часовой пояс GMT +6.
Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd. Перевод: zCarot

ВКонтактeTwitterFacebook
Хотите связаться с нами? Напишите письмо, и мы обязательно ответим.