我正在从事Consecutive Primes Challenge @ codeeval.com并且无法通过自动评分器。我认为我得到了正确的结果，但可能缺少一些边缘情况。我尝试了递归，但无法让它工作，而且速度太慢。通过创建具有偶数和奇数的两个数组找到了另一种解决方案。请让我知道这是否是一个可行的解决方案，如果你能看到错误。
以下是挑战说明：
爱丽丝有偶数 N 颗珠子，每颗珠子上都涂有从 1 到 N 的数字。她想用所有的珠子做一条项链，有一个特殊的要求：项链上任意两颗相邻的珠子之和必须是质数。爱丽丝需要你的帮助来计算有多少种方法可以做到这一点。
例如：
N = 4
有两种可能的方法来制作项链。请注意，最后一个珠子连接到第一个珠子。
1 2 3 4 1 4 3 2注意：项链应该是独一无二的。例如：与和
1 2 3 4相同。2 3 4 13 4 1 24 1 2 3
由于 codeeval.com 自动评分器的限制，该代码有一些 C 和 obj-c。这是我的代码：
BOOL isPrime(int number){
for(int i = 2;i<(int)(number/2)+1;i++){
if (number%i == 0) {
return false;
}
}
return true;
}
BOOL isEven(int number)
{
if(number%2==0){
return true;
}
return false;
}
NSMutableArray *createEvenNumbersArray(int num)
{
NSMutableArray *evenNumArray = [[NSMutableArray alloc]initWithCapacity:num];
for (int i=2; i<=num; i+=2) {
[evenNumArray addObject:[NSNumber numberWithInt:i]];
}
return evenNumArray;
}
NSMutableArray *createOddNumbersArray(int num)
{
NSMutableArray *oddNumArray = [[NSMutableArray alloc]initWithCapacity:num];
for (int i=3; i<=num; i+=2) {
[oddNumArray addObject:[NSNumber numberWithInt:i]];
}
return oddNumArray;
}
int calculateConsecutive(int input)
{
int count = 0;
BOOL evenFound = NO;
BOOL oddFound = NO;
NSMutableArray *oddNumArray = createOddNumbersArray(input); //creates odd number array with all the possiblities
NSMutableArray *evenNumArray = createEvenNumbersArray(input); // create even number array with all the possibilities
NSMutableArray *necklace = [[NSMutableArray alloc]init];
[necklace addObject:[NSNumber numberWithInt:1]]; // start the necklace with 1 to get rid of duplicate necklaces
for (int i = 2; i<=input; i+=2) { // goes through all the possibilities for the second bit to create the necklase
NSMutableArray *tempOddNumArray = [oddNumArray mutableCopy]; // populate odd number array
NSMutableArray *tempEvenNumArray = [evenNumArray mutableCopy]; // puplate even number array
if(isPrime([[necklace lastObject] intValue] + i)){
[tempEvenNumArray removeObject:[NSNumber numberWithInt:i]]; //remove number that we added to the necklase
[necklace addObject:[NSNumber numberWithInt:i]];
while ([necklace count]<=input) { // start creating the necklace after two numbers were added
oddFound = NO;
evenFound = NO;
for(NSNumber *oddNumber in tempOddNumArray){ // find the odd number possibility from the numbers that are left in the array
if(isPrime([[necklace lastObject] intValue] + oddNumber.intValue)){
[necklace addObject:oddNumber];
oddFound = YES;
break;
}
}
if (!oddFound) {
break;
}else{
[tempOddNumArray removeObject:[necklace lastObject]];
}
for(NSNumber *evenNumber in tempEvenNumArray){ // find the odd number possibility from the numbers that are left in the array
if(isPrime([[necklace lastObject] intValue] + evenNumber.intValue)){
[necklace addObject:evenNumber];
evenFound = YES;
break;
}
}
if (!evenFound) {
break;
}else{
[tempEvenNumArray removeObject:[necklace lastObject]];
}
if (([tempOddNumArray count] == 0) || ([tempEvenNumArray count] == 0) ){
break;
}
}
}
if (([necklace count] == input) && (isPrime([[necklace lastObject] intValue]+[[necklace firstObject] intValue]))) {
// check to make sure that the necklace is full and if the sum of the last number and first number is prime
count= count + 1;
}
NSLog(@"%@",necklace);
[necklace removeAllObjects];
[necklace addObject:[NSNumber numberWithInt:1]];
}
return count;
}
-(void)primesMain
{
int necklaceCount = 0;
int input = 18;
if (isEven(input)) {
necklaceCount = calculateConsecutive(input);
}
NSLog(@"%d",necklaceCount);
}
-(void)viewDidLoad
{
[self primesMain];
}
对于与代码审查网站的交叉发布，我深表歉意。我想获得有关代码的建议并找到错误。让我知道，我将删除其中一个论坛上的帖子。
谢谢！
=============== 更新
我在之前的代码中发现了错误。它真的没有遍历所有的可能性。现在我使用递归重写了代码。我得到不同的答案，但仍然不正确。Codeeval 通常使用 8 作为测试值，我得到 0 作为结果。我想知道这是否不正确。这是更新的代码
NSUInteger count=0; // using global variable so that i don't have to deal with counting in recursion for now anyway
BOOL isPrime(int number){
for(int i = 2;i<(int)(number/2)+1;i++){
if (number%i == 0) {
return false;
}
}
return true;
}
BOOL isEven(int number)
{
if(number%2==0){
return true;
}
return false;
}
void calculateNumNecklaces(int numOfBeads, NSMutableArray *beadsArray, NSMutableArray *necklace)
{
if ([beadsArray count] == 1) {
NSLog(@"%@",necklace);
if((isPrime([[necklace lastObject] intValue] + [[beadsArray lastObject] intValue]) && (isPrime([[necklace objectAtIndex:0] intValue] + [[beadsArray lastObject] intValue])))){
count +=1;
}
//return 1;
}else{
int previousNumber = [[necklace lastObject] intValue];
int startPos = 0;
if (isEven(previousNumber)){
if (isEven([[beadsArray objectAtIndex:0] intValue])) {
startPos = 1; //it will itterate through odd numbers only in the bead array by starting with the position where the odd number is
}
}else {
if (!isEven([[beadsArray objectAtIndex:0] intValue])) {
startPos = 1; //it will itterate through even numbers only in the bead array by starting with the position where the odd number is
}
}
for (int pos = startPos; pos < [beadsArray count]; pos+=2) {
if (isPrime(previousNumber + [[beadsArray objectAtIndex:pos] intValue])) {
NSMutableArray *tempNecklace = [necklace mutableCopy];
[tempNecklace addObject:[beadsArray objectAtIndex:pos]];
NSMutableArray *tempArray = [beadsArray mutableCopy];
[tempArray removeObjectAtIndex:pos];
//NSLog(@"%@",necklace);
calculateNumNecklaces(numOfBeads, tempArray, tempNecklace);
}
}
}
//return 0;
}
-(void)primesMain
{
int input = 6;
if (isEven(input)) {
NSMutableArray *beadsArray =[[NSMutableArray alloc] init];
for (int i = 2; i<=input; i++) {
[beadsArray addObject:[NSNumber numberWithInt:i]];
}
NSMutableArray *necklace = [[NSMutableArray alloc]init];
[necklace addObject:[NSNumber numberWithInt:1]];
calculateNumNecklaces(input, beadsArray, necklace);
}
NSLog(@"%d",count);
}