找出一个数的除数的最优化方法是什么,这样除数中至少有数字 3?
例如21=1,3,7,21
因此只有一个除数中有数字 3。
例如 62=1,2,31,62
因此只有一个除数中有数字 3,即 31
EDIT-i 意识到最好的方法是找出数字的所有因子并检查包含数字 3 的因子。
找出因素的最佳方法:
最佳答案
这是我的扩展。它首先检查列表中是否有可能的因素div3
.如果不是,它会将候选值添加到number/2,跳过已经可以根据此列表分解的值,因此添加“37”和“43”,但不添加“36”或“39” '.
以上部分应视为“设置”。如果知道输入约束(最大输入值),则可以计算 vector div3
一次,然后将其存储在程序中。
如果列表div3
是最新的,输入应该被分解为这些数字之一。如果不能,那么它的因子都不包含“3”。如果可以,则显示余数,可以使用常规方法进一步分解。
我认为这是“优化的”,因为首先检查了约束“任何因素都应包含‘3’”。只有找到任何有效因子,您才需要计算所有其他因子。
我的第一个程序使用 <vector>
和它的同类,所以在你的评论中要温和 :-)
(编辑)我现在注意到因子检查循环遍历了整个 div3
vector 。当然,只需要上到number/2
即可。 .作为练习留给读者。
(附加编辑)find3
这里是一个反向迭代器。出于某种原因,这似乎是合适的,但我不记得为什么我这么想 :) 如果检查并包括 number/2
,您需要将其更改为常规的前向迭代器。
#include <iostream>
#include <vector>
using namespace std;
int contains_3 (int value)
{
while (value && (value % 10) != 3)
value /= 10;
return value;
}
int main (int argc, char **argv)
{
int number, found_flag, last_div3, adjust, adjust_digit;
vector<int> div3;
vector<int>::reverse_iterator find3;
vector<int>::iterator it;
// a little seeding
div3.push_back(3);
div3.push_back(13);
div3.push_back(23);
if (argc != 2)
return -1;
number = atoi (argv[1]);
found_flag = 0;
// do we need to expand div3?
last_div3 = div3.back();
while (last_div3 * 2 < number)
{
// if this number contains a '3' in any other place than the last,
// simply increment it
if ((last_div3 % 10) != 9 && contains_3(last_div3/10))
{
last_div3++;
} else
{
// no? then simply pick the next multiple of 10 and add 3
last_div3 /= 10;
last_div3++;
last_div3 *= 10;
if (!contains_3(last_div3))
last_div3 += 3;
}
// check if it should be in the list
for (it = div3.begin() ; it != div3.end() && (last_div3 % *it); ++it) ;
if (it == div3.end())
{
div3.push_back(last_div3);
}
}
cout << "list is now: ";
for (it = div3.begin() ; it != div3.end(); ++it)
cout << ' ' << *it;
cout << endl;
for (find3 = div3.rbegin(); !found_flag && find3 != div3.rend(); find3++)
{
if (!(number % *find3))
{
cout << "candidate: " << *find3 << ", remaining to sieve: " << number/(*find3) << endl;
found_flag++;
}
}
if (!found_flag)
cout << "None found" << endl;
return 0;
}
关于c++ - 找出一个数的除数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19207932/