1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Тест "Счастливые билеты"

Тема в разделе "WASM.A&O", создана пользователем Intro, 7 сен 2021.

Метки:
  1. Intro

    Intro Active Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    295
    Оптимизация задачи.
    https://yadi.sk/d/zFoikkKNw2hDQw
    Можно выбрать от 0 до 8 изменив дефайн OPTIMIZATION.
    Время выполнения уменьшилось от 5 млн тактов и до 500-700, т.е. в 10 тысяч раз. Теперь задачу можно решить на любом утюге т.е. калькуляторе хоть на Б3-21.
    --- Сообщение объединено, 8 сен 2021 ---
    Базовый вариант, самый тупой, но зато понятный.
    Код (C):
    1.  
    2.     for(l3=0; l3<10; l3++)
    3.         for(l2=0; l2<10; l2++)
    4.             for(l1=0; l1<10; l1++)
    5.                 for(r3=0; r3<10; r3++)
    6.                     for(r2=0; r2<10; r2++)
    7.                         for(r1=0; r1<10; r1++)
    8.                             if (l1+l2+l3==r1+r2+r3)
    9.                                 count++;
    10.  
    Решил что сумму цифр надо вычислять там, где они меняются.
    Код (C):
    1.  
    2.    for(l3=0, sum_l=0; l3<10; l3++, sum_l-=9)
    3.         for(l2=0; l2<10; l2++, sum_l-=9)
    4.             for(l1=0; l1<10; l1++, sum_l++)
    5.                 for(r3=0, sum_r=0; r3<10; r3++, sum_r-=9)
    6.                     for(r2=0; r2<10; r2++, sum_r-=9)
    7.                         for(r1=0; r1<10; r1++, sum_r++)
    8.                             if (sum_l==sum_r)
    9.                                 count++;
    10.  
    Потом подумал что 686+ очень не любят условные переходы ака if'ы.
    Код (C):
    1.  
    2.     for(l3=0, sum_l=0; l3<10; l3++, sum_l-=9)
    3.         for(l2=0; l2<10; l2++, sum_l-=9)
    4.             for(l1=0; l1<10; l1++, sum_l++)
    5.                 for(r3=0, sum_r=0; r3<10; r3++, sum_r-=9)
    6.                     for(r2=0; r2<10; r2++, sum_r-=9)
    7.                         for(r1=0; r1<10; r1++, sum_r++)
    8.                             count += sum_l==sum_r;
    9.  
    Стало быстрей. Но это всё ерунда. Оптимизируем вариант 1.
    Можно легко доказать что условия count++ в цикле срабатывает только один раз или не разу, если сумма чисел в определённом диапазоне.
    Вот следующий вариант.
    Код (C):
    1.  
    2.     for(l3=0, sum_l=0; l3<10; l3++, sum_l-=9)
    3.         for(l2=0; l2<10; l2++, sum_l-=9)
    4.             for(l1=0; l1<10; l1++, sum_l++)
    5.                 for(r3=0, sum_r=0; r3<10; r3++, sum_r-=9)
    6.                     for(r2=0; r2<10; r2++, sum_r++)
    7.                         if (sum_l>=sum_r && sum_l<sum_r+10)
    8.                             count++;
    9.  
    Скорость заметно возросла. Но идём дальше, там уже по сложней.
    Далее такой вариант. Смотрим на эти ступеньки, и мысленно обваливаем её в пирамиду.
    Код (Text):
    1.  
    2. 0000000001111111111
    3. 000000001111111111
    4. 00000001111111111
    5. 0000001111111111
    6. 000001111111111
    7. 00001111111111
    8. 0001111111111
    9. 001111111111
    10. 01111111111
    11. 1111111111
    12.  
    Вертикальные столбики - это количество вариантов в этих диапазонах. А значит легко делаем следующий код.
    Код (C):
    1.  
    2.     for(l3=0, sum_l=0; l3<10; l3++, sum_l-=9)
    3.         for(l2=0; l2<10; l2++, sum_l-=9)
    4.             for(l1=0; l1<10; l1++, sum_l++)
    5.                 for(r3=0, sum_r=0; r3<10; r3++, sum_r++){
    6.                     int sum = sum_l - sum_r + 1;
    7.                     if (sum>0 && sum<20){
    8.                         count += sum;
    9.                         sum -= 10;
    10.                         if (sum>0)
    11.                             count -= 2*sum;
    12.                     }
    13.                 }
    14.  
    Ещё быстрей! И результат правильный. Но идём дальше.
    Теперь общая сумма вариантов равно не отдельному столбику, а суммы от левого края. Сумма половины пирамиды определяется так: (sum*sum+sum)/2. И по той же формуле отсекает в пирамиде лишние варианты.
    Получается код.
    Код (C):
    1.  
    2.     for(l3=0, sum_l=0; l3<10; l3++, sum_l-=9)
    3.         for(l2=0; l2<10; l2++, sum_l-=9)
    4.             for(l1=0; l1<10; l1++, sum_l++){
    5.                 int sum = sum_l + 1;
    6.                 count += (sum*sum+sum)/2;
    7.                 if (sum>10){
    8.                     sum -= 10;
    9.                     count -= ((sum*sum+sum)/2)*3;
    10.                     if (sum>10){
    11.                         sum -= 10;
    12.                         count += ((sum*sum+sum)/2)*3;
    13.                     }
    14.                 }
    15.             }
    16.  
    Стало ещё быстрей. Что дальше? Можно так.
    Код (C):
    1.  
    2.     for(sum_l=0; sum_l<=9*3; sum_l++){
    3.         int             sum = sum_l + 1;
    4.         unsigned int    count_l = (sum*sum+sum)/2;
    5.         if (sum>10){
    6.             sum -= 10;
    7.             count_l -= ((sum*sum+sum)/2)*3;
    8.             if (sum>10){
    9.                 sum -= 10;
    10.                 count_l += ((sum*sum+sum)/2)*3;
    11.             }
    12.         }
    13.         CountVar3[sum_l] = count_l;
    14.     }
    15.     for(l3=0, sum_l=0; l3<10; l3++, sum_l-=9)
    16.         for(l2=0; l2<10; l2++, sum_l-=9)
    17.             for(l1=0; l1<10; l1++, sum_l++)
    18.                 count += CountVar3[sum_l];
    19.  
    Быстрей, но что то не то. Может так.
    Код (C):
    1.  
    2.     for(sum_l=0; sum_l<=9*3; sum_l++){
    3.         int             sum = sum_l + 1;
    4.         unsigned int    count_l = (sum*sum+sum)/2;
    5.         if (sum>10){
    6.             sum -= 10;
    7.             count_l -= ((sum*sum+sum)/2)*3;
    8.             if (sum>10){
    9.                 sum -= 10;
    10.                 count_l += ((sum*sum+sum)/2)*3;
    11.             }
    12.         }
    13.         CountVar3[sum_l] = count_l;
    14.     }
    15.     for(sum_l=0; sum_l<=9*2; sum_l++){
    16.         int i;
    17.         unsigned int    count_l = CountVar3[sum_l];
    18.         for(i=1; i<10; i++)
    19.             count_l += CountVar3[sum_l+i];
    20.         CountVar2[sum_l] = count_l;
    21.     }
    22.     for(sum_l=0; sum_l<=9*1; sum_l++){
    23.         int i;
    24.         unsigned int    count_l = CountVar2[sum_l];
    25.         for(i=1; i<10; i++)
    26.             count_l += CountVar2[sum_l+i];
    27.         CountVar1[sum_l] = count_l;
    28.     }
    29.     for(l1=0; l1<10; l1++)
    30.         count += CountVar1[l1];
    31.  
    Не! Быстрей, но тоже не то.
    Ах да. Как же я упустил, задача то симметричная, мы вычислили вариант для одной стороны, а значит и для другой стороны такое количество вариантов. Значит надо просто возвести в квадрат.
    Вот вариант.
    Код (C):
    1.  
    2.     for(sum_l=0; sum_l<=9*3; sum_l++){
    3.         int             sum = sum_l + 1;
    4.         unsigned int    count_l = (sum*sum+sum)/2;
    5.         if (sum>10){
    6.             sum -= 10;
    7.             count_l -= ((sum*sum+sum)/2)*3;
    8.             if (sum>10){
    9.                 sum -= 10;
    10.                 count_l += ((sum*sum+sum)/2)*3;
    11.             }
    12.         }
    13.         count += count_l*count_l;
    14.     }
    15.  
    Так, да тут ещё можно в два раза уменьшить вариантов в цикле, а потом умножить на два. Но и так стало очень быстро. Теперь можно и для МК-61 программу составить, и он на своих 100 килогерцах решит достаточно быстро.
    Вот, как то так. Потом может лучше рисунками статью дополнить, чтобы попонятней было и выложить на хабре.
     
    Последнее редактирование: 8 сен 2021
    Intro, 7 сен 2021
    #1
  2. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    30
    У меня год назад, сильно зудело - хотелось переписать свой старый FFT алгоритм - пришла пара классных идей. Но увы, нет времени, пришлось включить волю и взять себя в руки. Отложил на потом. Иногда закрыв глаза, мечтаю о том, как переписываю алгоритм. :lol:
    А вам вот сейчас очень завидую. :mda:
     
    algent, 8 сен 2021
    #2