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