Важная информация
Показано с 1 по 5 из 5

Тема: заменить цикл for или как ускорить вычисление

  1. #1 заменить цикл for или как ускорить вычисление 
    Новичок
    Регистрация
    09.02.2012
    Сообщений
    4
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    подскажите по следующему вопросу
    есть вектор длиной 5 бит из него формирую расчитываю все возможные комбинации(вектора) длиной 2 бита затем с длиной 3, 4. При поиске всех возможных комбинаций длиной 2 бита использую в программе два for, когда 3 бита соотв 3 for и т д. Проблема возникает когда исходный вектор имеет длину 32 000 бит и из него я ищу все возможные комбинации длиной 23 бита т.е. в проге имею 23 for что в итоге очень долго. В матлабе есть аналогичная функция nchoosek но она с такими длинами не работает. Можно ли как то ускорить расчет заменой for или еще чем... Заранее спасибо...
    Ответить с цитированием  
     

  2. #2  
    Гуру Аватар для Абадябер
    Регистрация
    09.12.2010
    Адрес
    Беларусь, Минск
    Сообщений
    1,219
    Сказал(а) спасибо
    302
    Поблагодарили 176 раз(а) в 144 сообщениях
    Записей в блоге
    5
    Объясните, пожалуйста, что вы подразумеваете под словом "вектор"? И можете привести пример вектора, и некоторых возможных комбинаций? На примере мне будет легче разобраться, что именно вы хотите сделать.
    Дружба-магия-радость!
    Ответить с цитированием  
     

  3. #3  
    Новичок
    Регистрация
    09.02.2012
    Сообщений
    4
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    Цитата Сообщение от Абадябер Посмотреть сообщение
    Объясните, пожалуйста, что вы подразумеваете под словом "вектор"? И можете привести пример вектора, и некоторых возможных комбинаций? На примере мне будет легче разобраться, что именно вы хотите сделать.
    есть вектор 01010 (длиной 5 бит)
    индексы вектора 12345

    через цикл фор из вектора длиной 5 получаю все возможные комбинации длиной 2 бита
    т.е. следующие комбинации длиной 2
    12
    13
    14
    15
    23
    24
    25
    34
    35
    45
    затем хочу получить все комбинации длиной 3 бита, вот они
    1 2 3
    1 2 4
    1 2 5
    1 3 4
    1 3 5
    1 4 5
    2 3 4
    2 3 5
    2 4 5
    3 4 5

    соотв длиной 4 бита и это возможные комбинации
    1 2 3 4
    1 2 3 5
    1 2 4 5
    1 3 4 5
    2 3 4 5

    и последний длиной 5 это
    1 2 3 4 5

    в данном примере я взял веткор длиной 5 бит и работаю с индексами
    а у меня вектор длиной 4000 бит входной и получаю все возможные комбинации длиной 16 бит что при использовании форов очень долго как возможно ускорить вычисление... спасибо
    Ответить с цитированием  
     

  4. #4  
    Новичок
    Регистрация
    09.02.2012
    Сообщений
    4
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    немного разобрался правильно это называется размещение без повторений реализующая формулу n!/(n-k)!k! если есть быстродействующий алгоритм поделитесь у кого есть? спасибо
    Ответить с цитированием  
     

  5. #5  
    Новичок
    Регистрация
    09.02.2012
    Сообщений
    4
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    Вот нашел код, довольно неплохо работает но только на четыре порядка т.е n=2000 k=4
    дальше требуется много времени. Может как то оптимизировать можно этот код:

    #include <stdio.h>

    int a[2000];
    int na;

    int n, m; // total, to-take

    void step(int pos)
    {
    if(na==m) // one more completed
    {
    for(int i=0;i<na;i++)
    printf("%d ", a[i]+1); // тут записываю результат

    puts("");

    return;
    }

    if(pos+m-na > n) // won't be able to complete
    return;

    na++;

    for(int i = pos ? a[pos-1]+1 : 0; i<n; i++)
    a[na-1] = i, step(pos+1);

    na--;
    }

    int main()
    {
    scanf("%d %d", &n, &m);

    for(int i=0;i<n;i++)
    a[i] = i;

    step(0);
    }
    Ответить с цитированием  
     

Информация о теме
Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. цикл в цикле
    от 123456789igor в разделе Delphi
    Ответов: 8
    Последнее сообщение: 23.09.2012, 06:08
  2. excel в delphi цикл по строкам
    от 123456789igor в разделе Delphi
    Ответов: 4
    Последнее сообщение: 11.09.2012, 22:40
  3. Вычисление момента инерции
    от kostia-92 в разделе QBasic
    Ответов: 1
    Последнее сообщение: 26.06.2011, 05:18
  4. Ответов: 10
    Последнее сообщение: 10.01.2011, 22:05
  5. Вычисление числа пи
    от PreF1993 в разделе QBasic
    Ответов: 2
    Последнее сообщение: 17.12.2010, 21:51
Ваши права
  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •