算法尋找原始勾股數

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），而不會遇到這種情況三，你應該返回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; 
} 

，帶你更接近正確的程序，但你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; 
}