На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Перебор всех вариантов (сочетание ног насекомых) , простая задача с немного странным требованием полного перебора
    Всем хай! Сходу к делу!
    Условие задачи следующее: на берегу океана сидят и курят жуки и пауки, у которых вместе N ног. У каждого жука по 6 ног, а паука - 8 ног. Известно, что ног у всех жуков в К раз меньше, чем у всех пауков.
    Сколько всего жуков и пауков находится на берегу океана? N и К - натуральные числа. Если решений нет - выдать ответ ноль.


    строим мат.модель!
    х - кол-во жуков, y - кол-во пауков
    6х - всего ног у всех жуков
    8y - всего ног у всех пауков

    6x + 8y = N (1 необходимое условие)
    6x * K = 8y (2 необходимое условие)

    6x + 6x*K = N
    6x(1 + K) = N
    x = N / (6 + 6K)
    все, ГОТОВО. Данное уравнение имеет однозначное решение (если будет натуральное Х) иначе - нет решения.
    Проверим, пусть N = 360, K = 2.
    x = 360 / (6*3) = 360 / 18 = 20
    y = 6*20*2/8 = 30
    Итого: 20 + 30 = 50

    но есть одно НО(!), нужно решить задачу МЕТОДОМ ПОЛНОГО ПЕРЕБОРА.
    Что перебирать? ну, наверное {x, y}.
    Какие допустимые значения перебора х и y? Очевидно, что X(min) = Y(min) = 1.
    Нужно делать оценку допустимости X(max), Y(max).
    X(max) будет макс. при минимальном Y = 1.
    6*X(max) + 8 = N
    X(max) <= (N - 8)/6 - берем ближайшее натуральное снизу.

    Y(max) будем макс. при минимальном X = 1.
    6 + 8*Y(max) = N
    Y(max) <= (N - 6)/8 - берем ближайшее натуральное снизу.

    В итоге получаются такие переборы, да?
    for(x = 1 to X(max))
    for(y = 1 to Y(max))
    здесь подставляем текущие {x; y} в ОБА условия. Если выполнилось - ответ найден. Дальше можно не проверять, т к решение единственное (если оно есть)

    но есть еще одно НО(!), при возможности, нужно сократить варианты переборов (не до единственного).
    и вот у меня вопрос, здесь за счет чего варианты перебора можно сократить??

    добавить в эти циклы проверку
    for(x = 1 to X(max))
    for(y = 1 to Y(max))
    if(6x * K != 8Y) // дальше не считаем
    но вроде это НЕ сокращает варианты перебора...значения x, y также бегают от 1 до (max).

    Очень простая задача с очень странными требованиями решения через полный перебор, да, понимаю)
    подскажите как быть-то
      Ну, к примеру, можешь перебрать все возможные количества жуков, от нуля и до того, как число ног у жуков будет больше N.
      Далее подсчитываешь число ног жуков и пауков (6x и 6x*K) и сравниваешь их сумму с N. В принципе, если на этот момент суммарное число ног превысит N, то задача не сходится.

      И кстати, в твоём решении незачем брать натуральные снизу. Если задача решается, значит все частные ОБЯЗАНЫ быть целыми.
      Ну и N должно нацело делиться на 6*(K + 1)
        Цитата amk @
        к примеру, можешь перебрать все возможные количества жуков, от нуля и до того, как число ног у жуков будет больше N.

        я, кажись, понял, да, действительно, достаточно запустить лишь цикл по одним насекомым, а вторых искать в зависимости от первых...
        только НЕ от НУЛЯ, а от 1, т к кол-во ног насекомых - натуральные...ноги1 * K = ноги2

        Цитата amk @
        Если задача решается, значит все частные ОБЯЗАНЫ быть целыми.

        да, согласен, дробные "ноги" не рассматриваем, хотя еще подумаю потщательнее этот момент...

        Цитата amk @
        Ну и N должно нацело делиться на 6*(K + 1)

        это я закладывал и понимаю, просто не стал писать, т к это не влияет на кол-во переборов, просто, если не делится, то сразу ответ 0.

        в общем, вроде понятно, спс amk!

        P.S. еще были мысли, что нужно что-то мутить с разложением на простые делители N, K и пр., но ведать не придется, ну и хорошо!

        Добавлено
        вот прожка на с++, вроде все ОКейно!
        ExpandedWrap disabled
          #include <iostream>
           
          using namespace std;
           
          int main(void)
          {
              long long K, N;
              long long result = 0;
              
              cin >> N >> K;
              if(N % (6*K + 6) == 0)
              {
                  // наличие хотя бы одного жука и 1 паука гарантировано
                  for(long long x = 1; 6*x + 8 <= N; x++)
                      if((6*x + 6*x*K) == N)
                      {
                          result = x + 6*x*K/8;
                          break;
                      }
              }
           
              cout << endl << result << endl;
              fflush(stdin);
              cin.get();
           
              return 0;
          }

        т е предельное число переборов составляет (N - 8)/6. Кстати, N может на входе достигать 100 миллионов...(100 млн - 8)/6 примерно 11.5 млн переборов. Много это или мало, а черт его знает...но кажется, что многовато и нужна еще какая-то оптимизация.
          Цитата FasterHarder @

                  // наличие хотя бы одного жука и 1 паука гарантировано

          Для этого достаточно ненулевого K. Если жуков ноль - К не существует (деление на ноль), если пауков ноль, то К=0.

          При условии, что решение существует, конечно...
            тут с К все ок
            из условия следует, что x, y, K - натуральные числа

            вот, что делать с 11.5 милл.переборов (в худшем случае), хотя может это и не критично. Прогнал проггу на десятках миллионах N, результат появился сразу (там что-то получилось насекомых 235 000).
              Да я вообще не понимаю твоей заморочки по оптимизации учебной задачи с жёстко фиксированным (применение которого в данном конкретном случае есть явный [censored]) алгоритмом.
              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
              0 пользователей:


              Рейтинг@Mail.ru
              [ Script execution time: 0,0368 ]   [ 16 queries used ]   [ Generated: 19.03.24, 09:36 GMT ]