primes - 原始ピタゴラスの三重体を見つけるためのアルゴリズム

Question

ここに私のコードがあります:

// PPT.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

#define LOWER_BOUND 1
#define UPPER_BOUND 20

struct ppt
{
    int v1;
    int v2;
    int v3;
    ppt *next;
};

typedef struct ppt PPT;
typedef PPT *ppt_ptr;


void insert_ppt(ppt_ptr *h_ptr, ppt_ptr *t_ptr, int u1, int u2, int u3);

void print_ppt(ppt_ptr curr_ptr);

int is_prime(int n);

int is_pythagorean_triplet(int v1, int v2, int v3);

int different_triples(int v1, int v2, int v3,  int u1, int u2, int u3);  

int are_exact_multiples(int p, int q, int r,  int l, int m, int n);  

int is_unique_and_insertable(ppt_ptr curr_ptr, int v1, int v2, int v3);  

//====================================================================

int _tmain(int argc, _TCHAR* argv[])
{
    ppt_ptr head_ptr = NULL;
    ppt_ptr tail_ptr = NULL;

    for (int a = LOWER_BOUND;  a <= UPPER_BOUND; a++)
    {
        for (int b = LOWER_BOUND;  b <= UPPER_BOUND;  b++)
        {
            for (int c = LOWER_BOUND;  c <= UPPER_BOUND; c++)
            {
                if(is_pythagorean_triplet(a,b,c) == 1)
                {
                    if(head_ptr == NULL)
                    {
                        //printf("%d %d %d",a,b,c);
                        insert_ppt(&head_ptr,&tail_ptr,a,b,c);
                    }
                    //printf("%d %d %d",a,b,c);
                    if(is_unique_and_insertable(tail_ptr,a,b,c) == 1)
                    {   
                        //printf("%d %d %d\n",a,b,c);
                        insert_ppt(&head_ptr,&tail_ptr,a,b,c);
                    }
                }
            }
        }
    }

    //print_ppt(head_ptr);
    getchar();
    getchar();
    return 0;
}

この関数は、リストの最後に新しいノードを挿入します

void insert_ppt(ppt_ptr *h_ptr, ppt_ptr *t_ptr, int u1, int u2, int u3)
{
    ppt_ptr new_ptr;

    new_ptr = ppt_ptr( malloc( sizeof(PPT) ) );

    if(new_ptr != NULL)
    {
        new_ptr->v1   = u1;
        new_ptr->v2   = u2;
        new_ptr->v3   = u3;
        new_ptr->next = NULL;

        if(*h_ptr == NULL)
        {
            *h_ptr = new_ptr;
        }
        else
        {
            (*t_ptr)->next = new_ptr;
        }

        *t_ptr = new_ptr;
    }
    else
    {
        printf("%d %d %d not inserted. No memory available.\n",u1,u2,u3);
    }
}

この関数はリストを出力します

void print_ppt(ppt_ptr curr_ptr)
{
    if(curr_ptr == NULL)
    {
        printf("List is empty.\n\n");
    }
    else
    {
        while(curr_ptr != NULL)
        {
            printf("%d %d %d\n",curr_ptr->v1,curr_ptr->v2,curr_ptr->v3);
            curr_ptr = curr_ptr->next;
        }
    }
}

この関数は、数値が素数かどうかを判断します

// Function 1
int is_prime(int n)
{
    int num_of_factors = 0;
    int i = 1;

    for (i=1; i<=n; i++)
    {
        if (n % i  == 0)
        {
            num_of_factors ++;
        }
    }

    if (num_of_factors == 2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

この関数は、トリプレットがピタゴラスかどうかを判断します

// Function 2
int is_pythagorean_triplet(int v1, int v2, int v3)
{
    if ( (v1*v1 + v2*v2 == v3*v3) || (v2*v2 + v3*v3 == v1*v1) || (v1*v1 + v3*v3 == v2*v2) )
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

この関数は、トリプレットが一意であるかどうかを判断します。これは、私が問題を抱えている関数です

int is_unique_and_insertable(ppt_ptr curr_ptr, int v1, int v2, int v3)
{
    if(curr_ptr == NULL)
    {
        //printf("List is empty.\n\n");
    }
    else
    {
        if(curr_ptr != NULL)
        {
            //printf("%d %d %d\n",curr_ptr->v1,curr_ptr->v2,curr_ptr->v3);
            int u1 = curr_ptr->v1;
            int u2 = curr_ptr->v2;
            int u3 = curr_ptr->v3;

            if( (different_triples(v1,v2,v3,u1,u2,u3)) && 
                (!are_exact_multiples(v1,v2,v3,u1,u2,u3) ) )
            {
                printf("%d %d %d\n",curr_ptr->v1,curr_ptr->v2,curr_ptr->v3);
                return 1;
            }

            //printf("yoyoyo");
            curr_ptr = curr_ptr->next;
        }
    }
    return 0;
}

この関数は、トリプルが一意かどうかを判断します

// Definition:  This function checks if <v1,v2,v3> and <u1,u2,u3> are different triplets
//              or not.  If they are different triplets, it returns 1.
int different_triples(int v1, int v2, int v3,  int u1, int u2, int u3)
{
    if (v1==u1 && v2==u2 &&  v3==u3)
        return 0;
    else if (v1==u1 && v2==u3 && v3==u2)
        return 0;
    else if (v1==u2 && v2==u1 && v3==u3)
        return 0;
    else if (v1==u2 && v2==u3 && v3==u1)
        return
    else if (v1==u3 && v2==u2 && v3==u1)
        return 0;
    else if (v1==u3 && v2==u1 && v3==u2)
        return 0;
    else
        return 1;
}

この関数は、トリプレットがトリプレットの倍数であるかどうかを判別します

// This function tests if the triplet <p,q,r> is an exact multiple of <l,m,n> in any order
//   (arrangement/permutation)
int  are_exact_multiples(int v1, int v2, int v3,  int u1, int u2, int u3)
{
    if (v1%u1==0 && v2%u2==0 &&  v3%u3==0)
        return 1;
    else if (u1%v1==0 && u2%v2==0 &&  u3%v3==0)
        return 1;
    else if (v1%u1==0 && v2%u3==0 && v3%u2==0)
        return 1;
    else if (u1%v1==0 && u2%v3==0 && u3%v2==0)
        return 1;
    else if (v1%u2==0 && v2%u1==0 && v3%u3==0)
        return 1;
    else if (v1%u2==0 && v2%u3==0 && v3%u1==0)
        return 1;
    else if (u1%v2==0 && u2%v1==0 && u3%v3==0)
        return 1;
    else if (u1%v2==0 && u2%v3==0 && u3%v1==0)
        return 1;
    else if (v1%u3==0 && v2%u2==0 && v3%u1==0)
        return 1;
    else if (v1%u3==0 && v2%u1==0 && v3%u2==0)
        return 1;
    else if (u1%v3==0 && u2%v2==0 && u3%v1==0)
        return 1;
    else if (u1%v3==0 && u2%v1==0 && u3%v2==0)
        return 1;
    else
        return 0;
}

アルゴリズムが最適化されていないことはわかっています...後で行います。誰かがこのコードを機能させるのを手伝ってくれませんか?

Answer 1

関数is_unique_and_insertableはおそらく、同等のトリプル (異なる順序で同じ数字) がリストに既に存在するかどうか、または新しいトリプルがリスト内のトリプルの倍数 (モジュロ順列) であるかどうかを確認する必要があります。ただし、新しいトリプルを最初のリスト要素と比較するだけで、関数にはループ ステートメントや再帰はありません。

int is_unique_and_insertable(ppt_ptr curr_ptr, int v1, int v2, int v3)
{
    if(curr_ptr == NULL)
    {
        //printf("List is empty.\n\n");
    }
    else
    {
        if(curr_ptr != NULL)
        {
            //printf("%d %d %d\n",curr_ptr->v1,curr_ptr->v2,curr_ptr->v3);
            int u1 = curr_ptr->v1;
            int u2 = curr_ptr->v2;
            int u3 = curr_ptr->v3;

            if( (different_triples(v1,v2,v3,u1,u2,u3)) && 
                (!are_exact_multiples(v1,v2,v3,u1,u2,u3) ) )
            {
                printf("%d %d %d\n",curr_ptr->v1,curr_ptr->v2,curr_ptr->v3);
                return 1;
            }

            //printf("yoyoyo");
            curr_ptr = curr_ptr->next;
        }
    }
    return 0;
}

を使用した場合、最初の要素以上のものと比較することができますwhile(curr_ptr != NULL)。ただし、それでも間違ったロジックがあり、新しいトリプルが倍数ではない別のトリプルを見つけるとすぐに true (1) を返します。

ロジックは逆でなければなりません。同等のトリプル (または新しいトリプルがその倍数であるトリプル) に遭遇した場合、false (0) を返します。真を返す:

int is_unique_and_insertable(ppt_ptr curr_ptr, int v1, int v2, int v3)
{
    while(curr_ptr != NULL)
    {
        int u1 = curr_ptr->v1;
        int u2 = curr_ptr->v2;
        int u3 = curr_ptr->v3;
        if (!different_triples(v1, v2, v3, u1, u2, u3) || are_exact_multiples(v1, v2, v3, u1, u2, u3))
        {
            return 0;
        }
        curr_ptr = curr_ptr->next;
    }
    return 1;
}

これにより、正しいプログラムに近づきますが、関数に欠陥があり、 の倍数であるare_exact_multiplesと宣言されますが、そうではありません。(15, 36, 39)(3, 4, 5)

(a, b, c)のトリプルのみを考慮した場合、適切なプログラムを取得するのがはるかに単純で簡単になりますa <= b <= c(実際にはa < b < c、ピタゴラスのトリプルは 2 つの等しいコンポーネントを持つことができないため)。

あなたは後で効率を扱うと言っていましたが、すぐにそれをしてください。あなたのis_prime機能は非常に非効率的です。最初の非自明な除数を見つけたらすぐに停止する必要があり、平方根に到達したら停止できます。

int is_prime(int n)
{
    if (n < 2) return 0;
    if (n%2 == 0) return n == 2;
    for(int d = 3; d*d <= n; d += 2)
    {
        if (n%d == 0) return 0;
    }
    return 1;
}