2

背景：我正在使用 Matlab 处理 Project Euler问题 23，以练习我几乎不存在的编程技能。

我的问题：

现在我有一个包含大约 6500 个数字（范围从 12 到 28122）作为元素的向量，并且想要计算所有两个元素的总和。也就是说，我只需要每个总和的一个实例，因此计算了 a1 + an 后，就不必计算 an + a1。

编辑澄清：这包括总和 a1+a1、a2+a2、...、an+an。

问题是这太慢了。

问题特定约束：

无需计算总和 28123 或以上是给定的，因为这些不能用于进一步解决问题。

我的做法：

AbundentNumberSumsRaw=[];
for i=1:3490
    AbundentNumberSumsRaw=[AbundentNumberSumRaw AbundentNumbers(i)+AbundentNumbers(i:end);
end

这非常有效：p

我的评论：

我很确定逐渐增加向量 AbundentNumbersRaw 是不好的编码，因为这意味着内存使用量会不必要地飙升。我没有这样做，因为a）我不知道要预先分配什么大小的向量，b）我无法想出一种方法来有序地将总和注入 AbundentNumbersRaw 而不使用一些丑陋的嵌套循环。

"for i=1:3490" 低于元素的数量，仅仅是因为我检查并看到索引高于 3490 的数字的所有结果总和对于我来说太大而无法使用。

我很确定我的主要问题是程序需要对向量 AbundentNumbersRaw 进行大量增量增加。

任何和所有的帮助和建议将不胜感激:)

干杯

拉斯穆斯

4

3 回答 3

3

认为

a = 28110*rand(6500,1)+12;

然后

sums = [
 a(1) + a(1:end)
 a(2) + a(2:end)
 ... 
];

是您要进行的计算。

您还声明应丢弃值超过 28123 的总和。

这可以这样概括：

% Compute all 2-element sums without repetitions
C = arrayfun(@(x) a(x)+a(x:end), 1:numel(a), 'uniformoutput', false);
C = cat(1, C{:});

% discard sums exceeding threshold
C(C>28123) = [];

或使用循环

% Compute all 2-element sums without repetitions
E = cell(numel(a),1);
for ii = 1:numel(a)
    E{ii} = a(ii)+a(ii:end); end
E = cat(1, E{:});

% discard sums exceeding threshold
E(E>28123) = [];

简单的测试表明这arrayfun比循环要快一些，所以我会选择这个arrayfun选项。

于 2012-10-26T14:19:33.100 回答
0

由于您的主要问题是找出给定集合中的哪些整数可以写为不同集合的两个整数的总和，所以我会选择不同的方法：

AbundantNumbers = 1:6500; % replace with the list you generated somewhere else
maxInteger = 28122;
AbundantNumberSum(1:maxInteger) = true; % logical array

for i = 1:length(AbundantNumbers)
  sumIndices = AbundantNumbers(i) + AbundantNumbers;
  AbundantNumberSum(sumIndices(sumIndices <= maxInteger)) = false;
end

不幸的是，这不是对您的问题的回答，而是对您的问题的回答；-) 对于 MatLab 解决原始问题的方法，请参阅 Rody Oldenhuis 的优雅回答。

于 2012-10-26T14:31:45.017 回答
0

我的方法如下：

v = 1:3490;   % your vector here
s = length(v);
result = zeros(s);  % preallocate memory

for m = 1:s
     result(m,m:end) = v(m)+v(m:end);    
end

您将获得一个由 3490 x 3490 元素组成的矩阵，其中一半以上为 0。

于 2012-10-26T14:39:38.193 回答