0

here is my code:

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

this function inserts a new node at end of list

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

this function prints list

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

this function determines if a number is prime

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

this function determines if a triplet is pythagorean

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

this function determines if a triplet is unique and this is the function that i am having trouble with

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

this function determines if a triple is unique

// 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 determines if a triplet is a multiple of a triplet

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

I know that the algorithm is not optimized... i will do that later. Can somebody please help me get this code to work.

1
  • "the algorithm is not optimized" Understatement of the month :D Sep 13, 2012 at 11:51

1 Answer 1

0

Your function is_unique_and_insertable presumably should check whether an equivalent triple (the same numbers in different order) is already present in the list or the new triple is a multiple (modulo permutations) of a triple in the list. But it only compares the new triple to the first list element, there is no looping statement or recursion in the function.

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

You would get it to compare to more than just the first element if you used a while(curr_ptr != NULL). However, it would still have the wrong logic, it would return true (1) as soon as it finds a different triple the new one is not a multiple of.

The logic must be the other way round, if an equivalent triple (or a triple the new one is a multiple of) is encountered, then you return false (0), only if the entire list is traversed without encountering such a triple should you return true:

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

That takes you closer to a correct program, but your are_exact_multiples function is faulty, it would declare (15, 36, 39) to be a multiple of (3, 4, 5), although it isn't.

You would get a much simpler and easier to get right program if you only considered triples (a, b, c) with a <= b <= c (actually, a < b < c, since a Pythagorean triple can't have two equal components).

You said you would treat efficiency later, but please do that soon, your is_prime function is painfully inefficient. You should stop as soon as you found the first nontrivial divisor, and you can stop when you've reached the square root:

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;
}
2
  • thanks bro. code works. now i just have to optimize the pythagorean triple code... right now its at O(n^3) Sep 13, 2012 at 18:54
  • The easiest optimisation for that is to calculate c from a and b, makes it O(n^2) immediately. You can get much better if you use a parametrisation of Pythagorean triples. There's an easy classical one that was already known to the ancient Greeks. Sep 13, 2012 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.