连续质数挑战

Question

我正在连续质数挑战@ codeeval.com上工作，无法通过自动评分器。我认为我得到了正确的结果，但可能遗漏了一些边缘情况。我尝试过递归，但无法让它工作，而且太慢了。想出另一个解决方案，用偶数和奇数创建两个数组。请让我知道这是否是一个可行的解决方案，如果你能看到错误。

以下是对挑战的描述：

爱丽丝有一个偶数的N个珠子，每个珠子上有一个从1到N的数字。她想用所有的珠子做一条项链，有一个特殊的要求:项链上相邻的任何两个珠子都必须是质数。爱丽丝需要你的帮助来计算出有多少种方法可以做到这一点。 例如： N=4 这条项链有两种可能的制作方法。注意，最后一个珠连接到第一个珠。 1 2 3 4 1 4 3 2 注意:项链应该是独一无二的。例如：1 2 3 4与2 3 4 1、3 4 1 2和4 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);
}

Answer 1

这个程序是为了找出一个数组中有多少个连续数字(打牌)的可能性.

节目：

#include<iostream.h>
#include<conio.h>
void main()
   {
      int a[10],j,i,n,c,d;
      cin>>n;
       for(i=1;i<=n;i++)
         {
           cin>>a[i];
         }
 for(i=1;i<=n;i++)
  {
    for(j=1;j<=n-i;j++)
      {
         if(a[j]>a[j+1])
          {
            int temp;
            temp=a[j];
            a[j]=a[j+1];
             a[j+1]=temp;
           }
       }
       }
   for(j=1;j<=n;j++)
    {
      c=a[j]-a[j+1];
      d=a[j]-a[j+2];
          if(c==-1 && d==-2)
            {
                 cout<<a[j]<<a[j+1]<<a[j+2];
               }
          cout<<"\n";
      }
    getch();
   }

      output:
         input:
             a[i]={4,3,6,7,8,5}
         output:
                  345
                  456
                  567
                  678