0

这是我的代码：

// 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;
}

我知道算法没有优化......我稍后会这样做。有人可以帮我让这段代码工作吗？

4

1 回答 1

0

您的函数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). 然而，它仍然有错误的逻辑，一旦它找到一个不同的三元组，它就会返回真 (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，因为毕达哥拉斯三元组不能有两个相等的分量），您将获得一个更简单、更容易获得正确的程序。

你说你以后会处理效率，但请尽快这样做，你的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;
}
于 2012-09-13T12:49:19.997 回答