I'm trying to solve "small triangles, large triangles" code on hackerrank, but i'm not getting expected output

huangapple
go评论94阅读模式
英文:

I'm trying to solve "small triangles, large triangles" code on hackerrank, but i'm not getting expected output

问题

> 问题详情：- 给定 n 个三角形，具体来说，它们的边长分别是 a、b 和 c。按照它们的面积以相同的格式打印出来，从最小的面积到最大的面积排序。保证所有的面积都是不同的。

```c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct triangle
{
    int a;
    int b;
    int c;
};

struct temp_tri
{
    int a;
    int b;
    int c;
};

typedef struct triangle triangle;

void sort_by_area(triangle* tr, int n)
{
    int i, j, min;
    struct temp_tri tr_temp[100];
    double p[101], s[101], area[100];
    for (i=0; i<n; i++)
    {
        p[i] = (tr[i].a + tr[i].b + tr[i].c)*(0.5);
        s[i] = sqrt(p[i]*(p[i]-tr[i].a)*(p[i]-tr[i].b)*(p[i]-tr[i].c));
        area[i] = s[i];    
    }
    //To check whether areas are calculated correctly or not
    /*for (i=0; i<n; i++)
    {
        printf("%d %d %d :- %lf\n", tr[i].a, tr[i].b, tr[i].c, area[i]);
    }*/
    for (i=0; i<n; i++)
    {
        for (j=i+1; j<n; j++)
        {
            if (area[i] > area[j])
            {
                tr_temp[i].a = tr[i].a;
                tr[i].a = tr[j].a;
                tr[j].a = tr_temp[i].a;
                
                tr_temp[i].b = tr[i].b;
                tr[i].b = tr[j].b;
                tr[j].b = tr_temp[i].b;

                tr_temp[i].c = tr[i].c;
                tr[i].c = tr[j].c;
                tr[j].c = tr_temp[i].c;
            }
        }
    }
}     

int main()
{
    int n;
    printf("输入三角形数量：-\n");
    scanf("%d", &n);
    triangle *tr = malloc(n * sizeof(triangle));
    printf("输入 a、b、c：-\n");
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);
    }
    sort_by_area(tr, n);
    printf("\n");
    for (int i = 0; i < n; i++) {
        printf("%d %d %d\n", tr[i].a, tr[i].b, tr[i].c);
    }
    return 0;
}

实际输出（n = 10）：-

26 49 35
67 67 19
41 34 22
48 42 45
33 33 49
61 58 59
3 57 55 
23 43 35
63 46 45
23 12 27

期望输出：-

3 57 55
23 12 27
41 34 22
23 43 35
26 49 35
33 33 49
67 67 19
48 42 45
63 46 45
61 58 59


<details>
<summary>英文:</summary>

&gt; Problem details:- You are given n triangles, specifically, their sides a, b, and c . Print them in the same style but sorted by their areas from the smallest one to the largest one. It is guaranteed that all the areas are different.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct triangle
{
int a;
int b;
int c;
};

struct temp_tri
{
int a;
int b;
int c;
};

typedef struct triangle triangle;
void sort_by_area(triangle* tr, int n)
{
int i, j, min;
struct temp_tri tr_temp[100];
double p[101], s[101], area[100];
for (i=0; i<n; i++)
{
p[i] = (tr[i].a + tr[i].b + tr[i].c)(0.5);
s[i] = sqrt(p[i](p[i]-tr[i].a)(p[i]-tr[i].b)(p[i]-tr[i].c));
area[i] = s[i];
}
//To check whether areas are calculated correctly or not
/for (i=0; i<n; i++)
{
printf("%d %d %d :- %lf\n", tr[i].a, tr[i].b, tr[i].c, area[i]);
}/
for (i=0; i<n; i++)
{
for (j=i+1; j<n; j++)
{
if (area[i] > area[j])
{
tr_temp[i].a = tr[i].a;
tr[i].a = tr[j].a;
tr[j].a = tr_temp[i].a;

              tr_temp[i].b = tr[i].b;
              tr[i].b = tr[j].b;
              tr[j].b = tr_temp[i].b;

              tr_temp[i].c = tr[i].c;
              tr[i].c = tr[j].c;
              tr[j].c = tr_temp[i].c;
          }
      }
   }

}

int main()
{
int n;
printf("Enter no of triangles:- \n");
scanf("%d", &n);
triangle *tr = malloc(n * sizeof(triangle));
printf("Enter a, b, c:- \n");
for (int i = 0; i < n; i++) {
scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);
}
sort_by_area(tr, n);
printf("\n");
for (int i = 0; i < n; i++) {
printf("%d %d %d\n", tr[i].a, tr[i].b, tr[i].c);
}
return 0;
}

#### Actual output(n = 10):-

    26 49 35
    67 67 19
    41 34 22
    48 42 45
    33 33 49
    61 58 59
    3 57 55 
    23 43 35
    63 46 45
    23 12 27 

#### Expected output:-

    3 57 55
    23 12 27
    41 34 22
    23 43 35
    26 49 35
    33 33 49
    67 67 19
    48 42 45
    63 46 45
    61 58 59



</details>


# 答案1
**得分**: 4

你需要在你的冒泡排序实现中也交换区域：
```c
for (i = 0; i &lt; n; i++) {
    for (j = i + 1; j &lt; n; j++) {
        if (area[i] &gt; area[j]) {
            triangle tr_temp = tr[i];
            double area_temp = area[i];

            tr[i] = tr[j];
            area[i] = area[j];

            tr[j] = tr_temp;
            area[j] = area_temp;
        }
    }
}

另一种选择是将 area 添加到 struct triangle 中，这将简化排序过程：

struct triangle {
    int a;
    int b;
    int c;
    int area;
};
typedef struct triangle triangle;

void sort_by_area(triangle* tr, int n) {
    for (int i = 0; i &lt; n; i++) {
        double p = (tr[i].a + tr[i].b + tr[i].c) * (0.5);
        tr[i].area = sqrt(p * (p - tr[i].a) * (p - tr[i].b) * (p - tr[i].c));
    }
    for (int i = 0; i &lt; n; i++) {
        for (int j = i + 1; j &lt; n; j++) {
            if (tr[i].area &gt; tr[j].area) {
                triangle tr_temp = tr[i];
                tr[i] = tr[j];
                tr[j] = tr_temp;
            }
        }
    }
}

将 area 添加到 struct triangle 还使得可以轻松使用 qsort，当需要对大量要排序的三角形进行排序时，这将比冒泡排序快得多：

int triangle_comp(const void *lhs, const void *rhs) {
    const triangle *l = lhs, *r = rhs;
    if(l-&gt;area &lt; r-&gt;area) return -1;
    if(l-&gt;area &gt; r-&gt;area) return 1;
    return 0;
}

void sort_by_area(triangle* tr, int n) {
    for (int i = 0; i &lt; n; i++) {
        double p = (tr[i].a + tr[i].b + tr[i].c) * (0.5);
        tr[i].area = sqrt(p * (p - tr[i].a) * (p - tr[i].b) * (p - tr[i].c));
    }
    qsort(tr, n, sizeof *tr, triangle_comp);
}
英文:

You need to swap the area too in your bubble sort implementation:

for (i = 0; i &lt; n; i++) {
    for (j = i + 1; j &lt; n; j++) {
        if (area[i] &gt; area[j]) {
            triangle tr_temp = tr[i];
            double area_temp = area[i];

            tr[i] = tr[j];
            area[i] = area[j];

            tr[j] = tr_temp;
            area[j] = area_temp;
        }
    }
}

Another option could be to add area to struct triangle which would simplify the sorting:

struct triangle {
    int a;
    int b;
    int c;
    int area;
};
typedef struct triangle triangle;

void sort_by_area(triangle* tr, int n) {
    for (int i = 0; i &lt; n; i++) {
        double p = (tr[i].a + tr[i].b + tr[i].c) * (0.5);
        tr[i].area = sqrt(p * (p - tr[i].a) * (p - tr[i].b) * (p - tr[i].c));
    }
    for (int i = 0; i &lt; n; i++) {
        for (int j = i + 1; j &lt; n; j++) {
            if (tr[i].area &gt; tr[j].area) {
                triangle tr_temp = tr[i];
                tr[i] = tr[j];
                tr[j] = tr_temp;
            }
        }
    }
}

Adding area to struct triangle would also make it easy to instead use qsort which will be a lot faster than bubblesort when there are a great number of triangles that should be sorted:

int triangle_comp(const void *lhs, const void *rhs) {
    const triangle *l = lhs, *r = rhs;
    if(l-&gt;area &lt; r-&gt;area) return -1;
    if(l-&gt;area &gt; r-&gt;area) return 1;
    return 0;
}

void sort_by_area(triangle* tr, int n) {
    for (int i = 0; i &lt; n; i++) {
        double p = (tr[i].a + tr[i].b + tr[i].c) * (0.5);
        tr[i].area = sqrt(p * (p - tr[i].a) * (p - tr[i].b) * (p - tr[i].c));
    }
    qsort(tr, n, sizeof *tr, triangle_comp);
}

答案2

得分: 2

注意：如果你不释放分配的内存，竞赛网站可能会扣分...

你声明了两个不同的struct，并在代码中都使用了它们，尽管它们具有完全相同的成员。这被称为“维护噩梦”。保持代码尽可能清晰。

当Ted在键入他的编辑时，以下内容正在准备中。

正如@user3386109在评论中指出的，还需要交换三角形的尺寸时交换计算的面积。

以下内容与@Ted的回复类似，但包括一个额外的版本，使用“编译时初始化”数据值。这可以节省大量与输入或重定向相关的工作，使人能够专注于算法。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct triangle {
	int a;
	int b;
	int c;
	double area; // "area"是每个三角形的有效维度
} triangle;

/* 下一个函数的注释告诉读者在哪里查找有关正在使用的算法的更多信息...
*/
void calc_areas( triangle* tr, int n ) {
    // 使用“海伦公式”从3边计算面积
	for( int i = 0; i < n; i++ ) {
		double hlfPrm = ( tr[i].a + tr[i].b + tr[i].c ) * 0.5;
		tr[i].area = sqrt( hlfPrm * (hlfPrm-tr[i].a) * (hlfPrm-tr[i].b) * (hlfPrm-tr[i].c) );
	}
}

// 使用qsort()而不是重新编写排序算法
int cmp( const void *p1, const void *p2 ) {
	const triangle *pa = p1;
	const triangle *pb = p2;

	if( pa->area > pb->area ) return  1;
	if( pa->area < pb->area ) return -1;
	return 0;
}

int main( void ) {
	int n, i;

#ifdef KEYBOARD // 键盘输入或从文件重定向的版本。
	printf( "输入三角形数量：\n" );
	if( scanf( "%d", &n ) != 1 )
		return 1; // 改进错误处理

	triangle *tr = malloc( n * sizeof *tr );
	if( tr == NULL )
		return 1; // 改进错误处理

    // 始终测试返回代码，特别是对于用户输入！
	printf( "输入a、b、c：\n" );
	for( i = 0; i < n; i++ )
		if( scanf( "%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c ) != 3 )
			return 1; // 改进错误处理
#else // 编译时数据初始化
	triangle tr[] = {
		{ 26, 49, 35, },
		{ 67, 67, 19, },
		{ 41, 34, 22, },
		{ 48, 42, 45, },
		{ 33, 33, 49, },
		{ 61, 58, 59, },
		{  3, 57, 55, },
		{ 23, 43, 35, },
		{ 63, 46, 45, },
		{ 23, 12, 27, },
	};
	n = sizeof tr / sizeof tr[0];
#endif

	calc_areas( tr, n );
	qsort( tr, n, sizeof tr[0], cmp );

	for( i = 0; i < n; i++ )
		printf( "%8.2f = %2d %2d %2d\n", tr[i].area, tr[i].a, tr[i].b, tr[i].c );

#ifdef KEYBOARD
    free( tr );
#endif
	return 0;
}

输出：

   62.59 =  3 57 55
137.29 = 23 12 27
373.86 = 41 34 22
401.80 = 23 43 35
437.49 = 26 49 35
541.64 = 33 33 49
630.07 = 67 67 19
869.02 = 48 42 45
1034.11 = 63 46 45
1522.35 = 61 58 59
英文:

Note: Competition websites will likely fault you if you don't release allocated memory...

You've declared two different struct's, and use both in your code, even though they have exactly the same elements. This is known as a "maintenance nightmare." Keep code as clean as possible.

While Ted was typing his edits, the following was being prepared.

As pointed out in the comment by @user3386109, what's missing is also swapping the calculated areas when swapping the triangles' dimensions.

The following is much like @Ted's response, but includes an extra version that uses "compile time initialisation" of the data values. This saves a lot of mucking around with typing or redirection, allowing one to focus on the algorithm.

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;math.h&gt;
typedef struct triangle {
int a;
int b;
int c;
double area; // &quot;area&quot; is a valid dimension of each triangle
} triangle;
/*  Notice the comment in the next function that tells the reader
where to look for more info about the algorithm being used...
*/
void calc_areas( triangle* tr, int n ) {
// Using &quot;Heron&#39;s formula&quot; to derive area from 3 sides
for( int i = 0; i &lt; n; i++ ) {
double hlfPrm = ( tr[i].a + tr[i].b + tr[i].c ) * 0.5;
tr[i].area = sqrt( hlfPrm * (hlfPrm-tr[i].a) * (hlfPrm-tr[i].b) * (hlfPrm-tr[i].c) );
}
}
// use qsort() instead of retyping a sorting algorithm
int cmp( const void *p1, const void *p2 ) {
const triangle *pa = p1;
const triangle *pb = p2;
if( pa-&gt;area &gt; pb-&gt;area ) return  1;
if( pa-&gt;area &lt; pb-&gt;area ) return -1;
return 0;
}
int main( void ) {
int n, i;
#ifdef KEYBOARD // version of keyboard entry or redirection from a file.
printf( &quot;Enter no of triangles:- \n&quot; );
if( scanf( &quot;%d&quot;, &amp;n ) != 1 )
return 1; // improve error handling
triangle *tr = malloc( n * sizeof *tr );
if( tr == NULL )
return 1; // improve error handling
// ALWAYS test return codes, especially for user input!!
printf( &quot;Enter a, b, c:- \n&quot; );
for( i = 0; i &lt; n; i++ )
if( scanf( &quot;%d%d%d&quot;, &amp;tr[i].a, &amp;tr[i].b, &amp;tr[i].c ) != 3 )
return 1; // improve error handling
#else // compile time data initialisation
triangle tr[] = {
{ 26, 49, 35, },
{ 67, 67, 19, },
{ 41, 34, 22, },
{ 48, 42, 45, },
{ 33, 33, 49, },
{ 61, 58, 59, },
{  3, 57, 55, },
{ 23, 43, 35, },
{ 63, 46, 45, },
{ 23, 12, 27, },
};
n = sizeof tr / sizeof tr[0];
#endif
calc_areas( tr, n );
qsort( tr, n, sizeof tr[0], cmp );
for( i = 0; i &lt; n; i++ )
printf( &quot;%8.2f = %2d %2d %2d\n&quot;, tr[i].area, tr[i].a, tr[i].b, tr[i].c );
#ifdef KEYBOARD
free( tr );
#endif
return 0;
}

Output:

   62.59 =  3 57 55
137.29 = 23 12 27
373.86 = 41 34 22
401.80 = 23 43 35
437.49 = 26 49 35
541.64 = 33 33 49
630.07 = 67 67 19
869.02 = 48 42 45
1034.11 = 63 46 45
1522.35 = 61 58 59

huangapple
  • 本文由 发表于 2023年8月5日 13:06:30
  • 转载请务必保留本文链接：https://go.coder-hub.com/76840211.html
  • c
  • if-statement
  • struct
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定