dxdy.ru

Вычислительная сложность сумм и разностей : Помогите решить / разобраться (М)

  • ️Thu Feb 23 2023

Сообщения без ответов | Активные темы | Избранное




 

Вычислительная сложность сумм и разностей

Сообщение29.01.2025, 11:32 

23/02/23
145

Профиль  

dgwuqtj 

Re: Вычислительная сложность сумм и разностей

Сообщение29.01.2025, 12:00 

Заслуженный участник

07/08/23
1352

Профиль  

wrest 

Re: Вычислительная сложность сумм и разностей

Сообщение29.01.2025, 12:27 

05/09/16
12274

zgemm

Спросил у парочки ИИ, оба предлагают 7 операций. Один из них в качестве одной из 7 операций предлагает удвоение, что для целых чисел просто сдвиг на один бит.


Профиль  

mihaild 

Re: Вычислительная сложность сумм и разностей

Сообщение29.01.2025, 12:44 

Заслуженный участник
Аватара пользователя

16/07/14
9417
Цюрих

Можно не графы перебирать, а множества "что вообще можно посчитать за 6 действий", их чуть меньше.


Профиль  

Sender 

Re: Вычислительная сложность сумм и разностей

Сообщение29.01.2025, 13:09 

14/01/11
3126

Спросил у парочки ИИ, оба предлагают 7 операций.

Нынешние ИИ довольно неважно проявляют себя в задачах подобного рода.


Профиль  

dgwuqtj 

Re: Вычислительная сложность сумм и разностей

Сообщение29.01.2025, 15:02 

Заслуженный участник

07/08/23
1352

Я всё перебрал, за 6 сложений и вычитаний (и сколько угодно унарных вычитаний) действительно не получается. Программа работает несколько минут и выводит в консоль количество перебранных вариантов, когда оно делится на миллион.

#include <stdio.h>
#include <stdlib.h>
int coefficients[10][4]; // coefficients in the linear combinations of variables
long long count = 0; // current number of variants
FILE* output;

void try(int position) {
        if (position == 10) {
                count++;
                if (count % 1000000 == 0) {
                        printf("%d'000'000\n", (int)(count / 1000000));
                        fflush(stdout);
                }
                int done[3]; // flags if the required sums appeared
                done[0] = done[1] = done[2] = 0;
                for (int i = 4; i < position; i++) {
                        if ((long long)coefficients[i][0] * (long long)coefficients[i][1] * (long long)coefficients[i][2] * (long long)coefficients[i][3] == 1) {
                                if (coefficients[i][0] == coefficients[i][1]) {
                                        if (coefficients[i][0] == coefficients[i][2])
                                                done[2] = 1;
                                        else
                                                done[0] = 1;
                                } else {
                                        if (coefficients[i][0] != coefficients[i][2])
                                                done[1] = 1;
                                }
                        }
                        if (done[0] && done[1] && done[2]) {
                                for (int i = 4; i < position; i++) {
                                        for (int j = 0; j < 4; j++) {
                                                fprintf(output, "%d", coefficients[i][j]);
                                                if (j < 3)
                                                        fprintf(output, ", ");
                                        }
                                        if (i < position - 1)
                                                fprintf(output, "\n");
                                }
                                fclose(output);
                                exit(0);
                        }
                }
        } else {
                for (int i = 0; i < position; i++)
                        for (int j = 0; j < i; j++) {
                                for (int k = 0; k < 4; k++)
                                        coefficients[position][k] = coefficients[i][k] - coefficients[j][k];
                                try(position + 1);
                        }
                for (int i = 0; i < position; i++)
                        for (int j = 0; j <= i; j++) {
                                for (int k = 0; k < 4; k++)
                                        coefficients[position][k] = coefficients[i][k] + coefficients[j][k];
                                try(position + 1);
                        }
        }
}

int main() {
        output = fopen("output.txt", "w");
        for (int i = 0; i < 4; i++)
                for (int j = 0; j < 4; j++)
                        coefficients[i][j] = (i == j) ? 1 : 0;
        try(4);
        fclose(output);
}


Профиль  

zgemm 

Re: Вычислительная сложность сумм и разностей

Сообщение29.01.2025, 16:41 

23/02/23
145

Спасибо большое dgwuqtj

!!!

Я тоже начал писать аналогичную программу, но Вы опередили. Огромное спасибо!!!


Профиль  

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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