有必要创建一种算法来查找将自然数分解为自然数之和（至少 2）的方法数。
这个算法应该是一个特定的函数，它将一个自然数（2及以上）作为输入，并输出将该数分解为自然数之和（至少2）的方法数。
例如，对于数字 6，有 4 种方法：
6 = 6 = 2 + 4 = 3 + 3 = 2 + 2 + 2
我不需要束缚于特定的编程语言，重要的只是算法。
求和分解可以用图来表示，例如：
图上有 6 个顶点，每个顶点可以连接另外 2 个顶点（但至少 1 个），但不能关闭链：
因此，该函数将采用以下值：
f(1) = 0,
f(2) = 1,
f(3) = 1,
f(4) = 2,
f(5) = 2,
f(6) = 4,
f(7) = 4,
f(8) = 7,
f(9) = 8,
f(10) = 12,
<...>。
我也有兴趣了解序列的极限或函数相邻值之间关系序列的极限。
目前我知道如何计算连接所有顶点的方法数量，连接顶点以使图分为两部分，以及连接顶点以使图分为3部分。
为了您的学习，您需要比较经典的矩阵乘法算法和 Winograd-Strassen 算法。我不清楚为什么 Winograd-Strassen 算法比经典算法慢得多。据我所知，MatLab 对经典算法进行了更优化，尤其是对于超大型矩阵。使用 Winograd-Strassen 算法会浪费时间为中间矩阵等分配内存空间。但随着矩阵的大小，减速非常大 - 我将其附在图片中。图中，矩阵阶数为2^10的经典算法运行时间为几秒钟，而Winograd-Strassen算法则需要7分钟。
这是代码，可能算法没有正确理解它。只需使用 Strassen 和 Winograd-Strassen 算法调用一个函数就需要类型参数。好像没有更多的功能了
clc;
function AA = split_to_2x2_blocks(matrix) % разделение матрицы на 4 части
buf = width(matrix);
A11 = matrix(1:buf/2, 1:buf/2);
A12 = matrix(1:buf/2, buf/2+1:buf);
A21 = matrix(buf/2+1:buf, 1:buf/2);
A22 = matrix(buf/2+1:buf, buf/2+1:buf);
AA = {A11, A12
A21, A22};
end
function CC = strassen_mul_2x2(lb, rb, type) % умножение матрицы после разделения, рекурсивная чушь тут и все такое
d = strassen_mul(cell2mat(lb(1,1)) + cell2mat(lb(2,2)), cell2mat(rb(1,1)) + cell2mat(rb(2,2)), type);
d_1 = strassen_mul(cell2mat(lb(1,2)) - cell2mat(lb(2,2)), cell2mat(rb(2,1)) + cell2mat(rb(2,2)), type);
d_2 = strassen_mul(cell2mat(lb(2,1)) - cell2mat(lb(1,1)), cell2mat(rb(1,1)) + cell2mat(rb(1,2)), type);
left = strassen_mul(cell2mat(lb(2,2)), cell2mat(rb(2,1)) - cell2mat(rb(1,1)), type);
right = strassen_mul(cell2mat(lb(1,1)), cell2mat(rb(1,2)) - cell2mat(rb(2,2)), type);
top = strassen_mul(cell2mat(lb(1,1)) + cell2mat(lb(1,2)), cell2mat(rb(2,2)), type);
bottom = strassen_mul(cell2mat(lb(2,1)) + cell2mat(lb(2,2)), cell2mat(rb(1,1)), type);
c1 = d + d_1 + left - top;
c2 = right + top;
c3 = left + bottom;
c4 = d + d_2 + right - bottom;
CC = [c1, c2
c3, c4];
end
function CC = vinograd_strassen_mul_2x2(lb, rb, type)
s1 = cell2mat(lb(2,1)) + cell2mat(lb(2,2));
s2 = s1 - cell2mat(lb(1,1));
s3 = cell2mat(lb(1,1)) - cell2mat(lb(2,1));
s4 = cell2mat(lb(1,2)) - s2;
s5 = cell2mat(rb(1,2)) - cell2mat(rb(1,1));
s6 = cell2mat(rb(2,2)) - s5;
s7 = cell2mat(rb(2,2)) - cell2mat(rb(1,2));
s8 = s6 - cell2mat(rb(2,1));
p1 = strassen_mul(s2, s6, type);
p2 = strassen_mul(cell2mat(lb(1,1)), cell2mat(rb(1,1)), type);
p3 = strassen_mul(cell2mat(lb(1,2)), cell2mat(rb(2,1)), type);
p4 = strassen_mul(s3, s7, type);
p5 = strassen_mul(s1, s5, type);
p6 = strassen_mul(s4, cell2mat(rb(2,2)), type);
p7 = strassen_mul(cell2mat(lb(2,2)), s8, type);
t1 = p1 + p2;
t2 = t1 + p4;
CC = [p2 + p3, t1 + p5 + p6
t2 - p7, t2 + p5];
end
function c = default_mul(left, right) % классический метод умножения матриц
c = zeros(length(left));
for ii = 1:length(left)
for jj = 1:length(right)
for rr = 1:length(left)
c(ii, jj) = c(ii, jj) + left(ii, rr)* right(rr, jj);
end
end
end
end
function c = strassen_mul(left, right, type ) % типо сюда пихаем матрицу и её будущие части, а потом решаем
if length(left) == 2
c = default_mul(left, right);
else
%if type == 0
% c = strassen_mul_2x2(split_to_2x2_blocks(left), split_to_2x2_blocks(right), type);
%elseif type == 1
c = vinograd_strassen_mul_2x2(split_to_2x2_blocks(left), split_to_2x2_blocks(right), type);
%else
% disp('Не выбран вариант')
%end
end
end
%
% a = [1 2 3 4
% 5 6 7 8
% 9 10 11 12
% 13 14 15 16];
% b = [1 2 3 4
% 5 6 7 8
% 9 10 11 12
% 13 14 15 16];
% a = randi([1, 10], 8);
% b = randi([1, 10], 8);
% count_mas = [0, 0, 0]; % сложение, умножение, умножение матриц
% disp(a)
% disp(b)
% c = strassen_mul(a,b);
% disp(c)
% disp(sum)
% disp(umnoj)
% disp(umnoj_mat)
max_stepen = 6;
all_time = zeros(max_stepen, 2);
for t = 1:max_stepen
step = 2^t;
a = randi([1,10], step);
b = randi([1,10], step);
tic
c = default_mul(a, b);
all_time(t, 1) = toc;
tic
c = strassen_mul(a,b, 1);
all_time(t, 2) = toc;
end
t = 1:max_stepen;
hold on
grid on
title("График времени работы без фоновых процессов")
plot(t, all_time(:, 1),'-gs', 'LineWidth',2, 'MarkerSize',10,'Color', [0 0.4470 0.7410])
plot(t,all_time(:, 2),':gs','LineWidth',2,'MarkerSize',10, 'Color', [0.9290 0.6940 0.1250])
xlabel('Порядок матриц')
ylabel('Время работы')
legend("Классический метод", "Метод Винограда-Штрассена")
一只蚱蜢坐在一条长度为 n 的格子条前面。每个单元格包含一个数字。 KuznechiK 可以向前跳跃 1,2,... k 个单元格。您需要到达最右边的单元格，同时收集尽可能少的数量。输入是 n、k 和 n 个像元值。我不知道如何以最佳方式解决问题。目前，我只想使用该平台，在每个新单元格后添加一个新值，并在必要时删除旧单元格。但事实证明，每次我都必须在牌组中寻找新的最小值。有更好的选择吗？
我的代码解决了这个问题：
为什么通过引用 DFS 传递数组会导致内存限制，但全局声明它们会通过所有测试？
错误解决方法：
#include <bits/stdc++.h>
using namespace std;
vector <int> res;
int n, m;
void dfs(int v, vector<vector<int>> graph, vector<int> &used, vector<pair<int, int>> edges)
{
used[v] = 1;
for(int u:graph[v])
{
if(used[u] == 0)
{
for(int j = 1;j <= m;j++)
{
pair<int, int> p1 = {u, v};
pair<int, int> p2 = {v, u};
if(edges[j] == p1 || edges[j] == p2){
res.push_back(j);
break;
}
}
dfs(u, graph, used, edges);
}
}
}
int main()
{
int ind = 1;
cin >> n >> m;
vector <vector<int>> graph(n+1);
vector <int> used(n+1, 0);
vector <pair<int, int>> edges(m+1);
for(int i = 0;i < m;i++)
{
int t1, t2;
cin >> t1 >> t2;
graph[t1].push_back(t2);
graph[t2].push_back(t1);
edges[ind] = {t1, t2};
ind++;
}
dfs(1, graph, used, edges);
cout << res.size() << endl;
for(int x:res) cout << x << " ";
}
也许这是一个 XY 问题，尽管我个人不这么认为……
我们有一个平面无向图。本质上，将多边形分割成多个部分（这是 X :)）。任务是找到简单的（基本的，或者任何不包括其他的循环）循环（阅读 - 这些区域被划分成的区域。
例如，这是一个图表：
处理后，我需要类似向量的向量 - {2,6,11,10}，{6,11,5,7} 等。
我发现了一个类似的问题，但我不明白如何从那里获得我需要的东西。
初始问题：平面上有N个点，在这些点上有N个顶点的所有星形多边形中，找到面积最小的一个。这些区域是可能的星形多边形的核心。如果我找到了它们，那么将它们全部构建并找到合适的将是一项非常简单的任务。该图显示了点集 {1,2,3,4,5} 的内核。