[已解决]帮忙看一道题目

魔轩

问题描述
　　输入任意10个浮点数，根据它们的聚集程度划分为3组，输出每一组的平均值。
　　提供老师上课讲的一种思路：将10个数字进行在数轴上排序，然后计算每两个点间的距离，在所有的距离中选取两个最大距离处断开，这样就把10个数字分为了3组。
　　本题难度较大，如果深入讨论会比较复杂，大家可以只考虑如下面样例所示的分组情况非常简单的情况，只要简单情况能够成功计算，本题就能得分。
　　十个待输入的浮点数，使用空格隔开
输出格式
　　三组数的平均数，每输出一个需要换行
样例输入
一个满足题目要求的输入范例。
例1：
50.4 51.3 52.3 9.5 10.4 11.6 19.1 20.8 21.9 49.6

例2：
8.6 7.4 3.5 17.9 19.1 18.5 37.6 40.4 38.5 40.0
样例输出
与上面的样例输入对应的输出。
例1：
10.5
20.6
50.9

例2:
6.5
18.5
39.125
数据规模和约定
　　仅考虑如样例一样简单情况、分组明显的输入

最佳答案

月排行榜 / 总排行榜

人造人

2021-4-7 15:15:47

一共3个版本

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #include <math.h>
   
5. 
   
6. struct data_d_t {
   
7.     double *v;
   
8.     size_t s;
   
9. };
   
10. 
    
11. struct data_vd_t {
    
12.     struct data_d_t *v;
    
13.     size_t s;
    
14. };
    
15. 
    
16. struct data_ds_t {
    
17.     double d;
    
18.     size_t s;
    
19. };
    
20. 
    
21. struct data_pds_t {
    
22.     struct data_ds_t *v;
    
23.     size_t s;
    
24. };
    
25. 
    
26. int compar_d(const void *a, const void *b) {
    
27.     return *(const double *)a > *(const double *)b;
    
28. }
    
29. 
    
30. int compar_pds(const void *a, const void *b) {
    
31.     return ((const struct data_ds_t *)a)->s > ((const struct data_ds_t *)b)->s;
    
32. }
    
33. 
    
34. void free_d(struct data_d_t d) {
    
35.     free(d.v);
    
36. }
    
37. 
    
38. void free_vd(struct data_vd_t d) {
    
39.     for(size_t i = 0; i < d.s; ++i) {
    
40.         free_d(d.v[i]);
    
41.     }
    
42.     free(d.v);
    
43. }
    
44. 
    
45. void free_pds(struct data_pds_t d) {
    
46.     free(d.v);
    
47. }
    
48. 
    
49. void data_pds_insert(size_t i, struct data_pds_t *d, struct data_ds_t v) {
    
50.     memmove(&d->v[i + 1], &d->v[i], (d->s - i) * sizeof(v));
    
51.     d->v[i] = v;
    
52.     ++d->s;
    
53. }
    
54. 
    
55. void data_pds_append(struct data_pds_t *d, struct data_ds_t v) {
    
56.     d->v[d->s++] = v;
    
57. }
    
58. 
    
59. struct data_d_t create_data_d(const double *a, const double *b) {
    
60.     struct data_d_t result;
    
61.     result.v = malloc(sizeof(*result.v) * 100);
    
62.     result.s = 0;
    
63.     for(size_t i = 0; &a[i] != b; ++i) {
    
64.         result.v[i] = a[i];
    
65.         ++result.s;
    
66.     }
    
67.     return result;
    
68. }
    
69. 
    
70. struct data_d_t get_input(FILE *f, size_t s) {
    
71.     struct data_d_t d;
    
72.     d.s = 0;
    
73.     d.v = malloc(sizeof(*d.v) * 100);
    
74.     for(size_t i = 0; i < s; ++i) {
    
75.         double tmp;
    
76.         fscanf(f, "%lf", &tmp);
    
77.         d.v[i] = tmp;
    
78.         ++d.s;
    
79.     }
    
80.     return d;
    
81. }
    
82. 
    
83. struct data_pds_t get_max_distance(struct data_d_t d, size_t s) {
    
84.     struct data_pds_t result;
    
85.     result.v = malloc(sizeof(*result.v) * 100);
    
86.     result.s = 0;
    
87.     struct data_d_t distance;
    
88.     distance.s = d.s - 1;
    
89.     distance.v = malloc(sizeof(*distance.v) * distance.s);
    
90.     for(size_t i = 0; i < distance.s; ++i) {
    
91.         distance.v[i] = fabs(d.v[i] - d.v[i + 1]);
    
92.     }
    
93.     for(size_t i = 0; i < s; ++i) {
    
94.         struct data_ds_t tmp;
    
95.         tmp.d = distance.v[0];
    
96.         tmp.s = 0;
    
97.         result.v[i] = tmp;
    
98.         ++result.s;
    
99.         distance.v[0] = 0;
    
100.         for(size_t j = 1; j < distance.s; ++j) {
     
101.             struct data_ds_t *p = &result.v[i];
     
102.             if(distance.v[j] > p->d) {
     
103.                 distance.v[p->s] = p->d;
     
104.                 p->d = distance.v[j];
     
105.                 p->s = j;
     
106.                 distance.v[j] = j;
     
107.             }
     
108.         }
     
109.     }
     
110.     free_d(distance);
     
111.     return result;
     
112. }
     
113. 
     
114. struct data_vd_t get_groups(struct data_d_t d, size_t s) {
     
115.     struct data_vd_t result;
     
116.     result.v = malloc(sizeof(*result.v) * 100);
     
117.     result.s = 0;
     
118.     struct data_pds_t distance = get_max_distance(d, s - 1);
     
119.     qsort(distance.v, distance.s, sizeof(*distance.v), compar_pds);
     
120.     struct data_ds_t tmp;
     
121.     tmp.d = 0;
     
122.     tmp.s = -1;
     
123.     data_pds_insert(0, &distance, tmp);
     
124.     tmp.d = 0;
     
125.     tmp.s = d.s - 1;
     
126.     data_pds_append(&distance, tmp);
     
127.     for(size_t i = 0; i < distance.s - 1; ++i) {
     
128.         result.v[i] = create_data_d(&d.v[distance.v[i].s + 1], &d.v[distance.v[i + 1].s + 1]);
     
129.         ++result.s;
     
130.     }
     
131.     free_pds(distance);
     
132.     return result;
     
133. }
     
134. 
     
135. struct data_d_t get_average(struct data_vd_t d) {
     
136.     struct data_d_t result;
     
137.     result.v = malloc(sizeof(*result.v) * 100);
     
138.     result.s = 0;
     
139.     for(size_t i = 0; i < d.s; ++i) {
     
140.         double sum = 0;
     
141.         for(size_t j = 0; j < d.v[i].s; ++j) {
     
142.             sum += d.v[i].v[j];
     
143.         }
     
144.         result.v[i] = sum / d.v[i].s;
     
145.         ++result.s;
     
146.     }
     
147.     return result;
     
148. }
     
149. 
     
150. void print(struct data_d_t d) {
     
151.     for(size_t i = 0; i < d.s; ++i) {
     
152.         printf("%f ", d.v[i]);
     
153.     }
     
154.     printf("\n");
     
155. }
     
156. 
     
157. int main(void) {
     
158.     struct data_d_t raw_data = get_input(stdin, 10);
     
159.     qsort(raw_data.v, raw_data.s, sizeof(*raw_data.v), compar_d);
     
160.     struct data_vd_t group_data = get_groups(raw_data, 3);
     
161.     struct data_d_t average = get_average(group_data);
     
162.     print(average);
     
163.     free_d(average);
     
164.     free_vd(group_data);
     
165.     free_d(raw_data);
     
166.     return 0;
     
167. }
     

复制代码

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <math.h>
   
4. 
   
5. int compar_d(const void *a, const void *b) {
   
6.     return *(const double *)a > *(const double *)b;
   
7. }
   
8. 
   
9. void print(double data[], size_t size) {
   
10.     for(size_t i = 0; i < size; ++i) {
    
11.         printf("%f ", data[i]);
    
12.     }
    
13.     printf("\n");
    
14. }
    
15. 
    
16. int main(void) {
    
17.     double raw_buff[10];
    
18.     for(size_t i = 0; i < 10; ++i) {
    
19.         scanf("%lf", &raw_buff[i]);
    
20.     }
    
21.     qsort(raw_buff, 10, sizeof(*raw_buff), compar_d);
    
22.     size_t group_buff[2];
    
23.     //size_t group_size = get_groups(group_buff, raw_buff, 10);
    
24.     {
    
25.         double distance_buff[9];
    
26.         for(size_t i = 0; i < 9; ++i) {
    
27.             distance_buff[i] = fabs(raw_buff[i] - raw_buff[i + 1]);
    
28.         }
    
29.         for(size_t i = 0; i < 2; ++i) {
    
30.             size_t max_index = 0;
    
31.             for(size_t j = 1; j < 9; ++j) {
    
32.                 if(distance_buff[max_index] < distance_buff[j]) {
    
33.                     max_index = j;
    
34.                 }
    
35.             }
    
36.             distance_buff[max_index] = 0;
    
37.             group_buff[i] = max_index;
    
38.         }
    
39.         if(group_buff[0] > group_buff[1]) {
    
40.             size_t tmp = group_buff[0];
    
41.             group_buff[0] = group_buff[1];
    
42.             group_buff[1] = tmp;
    
43.         }
    
44.     }
    
45.     double average_buff[3];
    
46.     //size_t average_size = get_average(average_buff, raw_buff, group_buff, group_size);
    
47.     {
    
48.         {
    
49.             double sum = 0;
    
50.             for(size_t i = 0; i <= group_buff[0]; ++i) {
    
51.                 sum += raw_buff[i];
    
52.             }
    
53.             average_buff[0] = sum / (group_buff[0] + 1);
    
54.         }
    
55.         {
    
56.             double sum = 0;
    
57.             for(size_t i = group_buff[0] + 1; i <= group_buff[1]; ++i) {
    
58.                 sum += raw_buff[i];
    
59.             }
    
60.             average_buff[1] = sum / (group_buff[1] - group_buff[0]);
    
61.         }
    
62.         {
    
63.             double sum = 0;
    
64.             for(size_t i = group_buff[1] + 1; i <= 9; ++i) {
    
65.                 sum += raw_buff[i];
    
66.             }
    
67.             average_buff[2] = sum / (9 - group_buff[1]);
    
68.         }
    
69.     }
    
70.     print(average_buff, 3);
    
71.     return 0;
    
72. }
    

复制代码

跳转到最佳答案楼层

人造人

1. 没说用什么语言写，那就用C++写了
2. 完全按照你们老师的思路写的
3. 没有注释，^_^

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <cmath>
   
5. 
   
6. const std::vector<double> get_input(std::istream &is, size_t size) {
   
7.     std::vector<double> v;
   
8.     for(size_t i = 0; i < size; ++i) {
   
9.         double tmp; is >> tmp;
   
10.         v.push_back(tmp);
    
11.     }
    
12.     return v;
    
13. }
    
14. 
    
15. const std::vector<std::pair<double, size_t>> get_max_distance(const std::vector<double> &lhs, size_t size) {
    
16.     std::vector<std::pair<double, size_t>> result;
    
17.     std::vector<double> distance(lhs.size() - 1);
    
18.     for(size_t i = 0; i < distance.size(); ++i) {
    
19.         distance[i] = std::fabs(lhs[i] - lhs[i + 1]);
    
20.     }
    
21.     for(size_t i = 0; i < size; ++i) {
    
22.         result.push_back(std::pair<double, size_t>(distance[0], 0));
    
23.         distance[0] = 0;
    
24.         for(size_t j = 1; j < distance.size(); ++j) {
    
25.             auto p = result.end() - 1;
    
26.             if(distance[j] > p->first) {
    
27.                 distance[p->second] = p->first;
    
28.                 p->first = distance[j];
    
29.                 p->second = j;
    
30.                 distance[j] = 0;
    
31.             }
    
32.         }
    
33.     }
    
34.     return result;
    
35. }
    
36. 
    
37. const std::vector<std::vector<double>> get_groups(const std::vector<double> &v, size_t size) {
    
38.     std::vector<std::vector<double>> result;
    
39.     std::vector<std::pair<double, size_t>> distance = get_max_distance(v, size - 1);
    
40.     std::sort(distance.begin(), distance.end(), [](const std::pair<double, size_t> &a, \
    
41.                 const std::pair<double, size_t> &b) -> bool {return a.second < b.second;});
    
42.     distance.insert(distance.begin(), std::pair<double, size_t>(0, -1));
    
43.     distance.push_back(std::pair<double, size_t>(0, v.size() - 1));
    
44.     for(size_t i = 0; i < distance.size() - 1; ++i) {
    
45.         result.push_back(std::vector<double>(v.begin() + distance[i].second + 1, v.begin() + distance[i + 1].second + 1));
    
46.     }
    
47.     return result;
    
48. }
    
49. 
    
50. std::vector<double> get_average(const std::vector<std::vector<double>> &data) {
    
51.     std::vector<double> v;
    
52.     for(auto iter = data.begin(); iter != data.end(); ++iter) {
    
53.         double sum = 0;
    
54.         for(const auto &j: *iter) sum += j;
    
55.         v.push_back(sum / iter->size());
    
56.     }
    
57.     return v;
    
58. }
    
59. 
    
60. std::ostream &operator<<(std::ostream &os, const std::vector<double> &rhs) {
    
61.     for(const auto &i: rhs) os << i << " ";
    
62.     return os;
    
63. }
    
64. 
    
65. int main() {
    
66.     std::vector<double> raw_data = get_input(std::cin, 10);
    
67.     std::sort(raw_data.begin(), raw_data.end());
    
68.     std::vector<std::vector<double>> group_data = get_groups(raw_data, 3);
    
69.     std::cout << get_average(group_data) << std::endl;
    
70.     return 0;
    
71. }
    

复制代码

魔轩

人造人 发表于 2021-4-4 20:38
1. 没说用什么语言写，那就用C++写了
2. 完全按照你们老师的思路写的
3. 没有注释，^_^

可以换成c吗，这看不懂

人造人

一共3个版本

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #include <math.h>
   
5. 
   
6. struct data_d_t {
   
7.     double *v;
   
8.     size_t s;
   
9. };
   
10. 
    
11. struct data_vd_t {
    
12.     struct data_d_t *v;
    
13.     size_t s;
    
14. };
    
15. 
    
16. struct data_ds_t {
    
17.     double d;
    
18.     size_t s;
    
19. };
    
20. 
    
21. struct data_pds_t {
    
22.     struct data_ds_t *v;
    
23.     size_t s;
    
24. };
    
25. 
    
26. int compar_d(const void *a, const void *b) {
    
27.     return *(const double *)a > *(const double *)b;
    
28. }
    
29. 
    
30. int compar_pds(const void *a, const void *b) {
    
31.     return ((const struct data_ds_t *)a)->s > ((const struct data_ds_t *)b)->s;
    
32. }
    
33. 
    
34. void free_d(struct data_d_t d) {
    
35.     free(d.v);
    
36. }
    
37. 
    
38. void free_vd(struct data_vd_t d) {
    
39.     for(size_t i = 0; i < d.s; ++i) {
    
40.         free_d(d.v[i]);
    
41.     }
    
42.     free(d.v);
    
43. }
    
44. 
    
45. void free_pds(struct data_pds_t d) {
    
46.     free(d.v);
    
47. }
    
48. 
    
49. void data_pds_insert(size_t i, struct data_pds_t *d, struct data_ds_t v) {
    
50.     memmove(&d->v[i + 1], &d->v[i], (d->s - i) * sizeof(v));
    
51.     d->v[i] = v;
    
52.     ++d->s;
    
53. }
    
54. 
    
55. void data_pds_append(struct data_pds_t *d, struct data_ds_t v) {
    
56.     d->v[d->s++] = v;
    
57. }
    
58. 
    
59. struct data_d_t create_data_d(const double *a, const double *b) {
    
60.     struct data_d_t result;
    
61.     result.v = malloc(sizeof(*result.v) * 100);
    
62.     result.s = 0;
    
63.     for(size_t i = 0; &a[i] != b; ++i) {
    
64.         result.v[i] = a[i];
    
65.         ++result.s;
    
66.     }
    
67.     return result;
    
68. }
    
69. 
    
70. struct data_d_t get_input(FILE *f, size_t s) {
    
71.     struct data_d_t d;
    
72.     d.s = 0;
    
73.     d.v = malloc(sizeof(*d.v) * 100);
    
74.     for(size_t i = 0; i < s; ++i) {
    
75.         double tmp;
    
76.         fscanf(f, "%lf", &tmp);
    
77.         d.v[i] = tmp;
    
78.         ++d.s;
    
79.     }
    
80.     return d;
    
81. }
    
82. 
    
83. struct data_pds_t get_max_distance(struct data_d_t d, size_t s) {
    
84.     struct data_pds_t result;
    
85.     result.v = malloc(sizeof(*result.v) * 100);
    
86.     result.s = 0;
    
87.     struct data_d_t distance;
    
88.     distance.s = d.s - 1;
    
89.     distance.v = malloc(sizeof(*distance.v) * distance.s);
    
90.     for(size_t i = 0; i < distance.s; ++i) {
    
91.         distance.v[i] = fabs(d.v[i] - d.v[i + 1]);
    
92.     }
    
93.     for(size_t i = 0; i < s; ++i) {
    
94.         struct data_ds_t tmp;
    
95.         tmp.d = distance.v[0];
    
96.         tmp.s = 0;
    
97.         result.v[i] = tmp;
    
98.         ++result.s;
    
99.         distance.v[0] = 0;
    
100.         for(size_t j = 1; j < distance.s; ++j) {
     
101.             struct data_ds_t *p = &result.v[i];
     
102.             if(distance.v[j] > p->d) {
     
103.                 distance.v[p->s] = p->d;
     
104.                 p->d = distance.v[j];
     
105.                 p->s = j;
     
106.                 distance.v[j] = j;
     
107.             }
     
108.         }
     
109.     }
     
110.     free_d(distance);
     
111.     return result;
     
112. }
     
113. 
     
114. struct data_vd_t get_groups(struct data_d_t d, size_t s) {
     
115.     struct data_vd_t result;
     
116.     result.v = malloc(sizeof(*result.v) * 100);
     
117.     result.s = 0;
     
118.     struct data_pds_t distance = get_max_distance(d, s - 1);
     
119.     qsort(distance.v, distance.s, sizeof(*distance.v), compar_pds);
     
120.     struct data_ds_t tmp;
     
121.     tmp.d = 0;
     
122.     tmp.s = -1;
     
123.     data_pds_insert(0, &distance, tmp);
     
124.     tmp.d = 0;
     
125.     tmp.s = d.s - 1;
     
126.     data_pds_append(&distance, tmp);
     
127.     for(size_t i = 0; i < distance.s - 1; ++i) {
     
128.         result.v[i] = create_data_d(&d.v[distance.v[i].s + 1], &d.v[distance.v[i + 1].s + 1]);
     
129.         ++result.s;
     
130.     }
     
131.     free_pds(distance);
     
132.     return result;
     
133. }
     
134. 
     
135. struct data_d_t get_average(struct data_vd_t d) {
     
136.     struct data_d_t result;
     
137.     result.v = malloc(sizeof(*result.v) * 100);
     
138.     result.s = 0;
     
139.     for(size_t i = 0; i < d.s; ++i) {
     
140.         double sum = 0;
     
141.         for(size_t j = 0; j < d.v[i].s; ++j) {
     
142.             sum += d.v[i].v[j];
     
143.         }
     
144.         result.v[i] = sum / d.v[i].s;
     
145.         ++result.s;
     
146.     }
     
147.     return result;
     
148. }
     
149. 
     
150. void print(struct data_d_t d) {
     
151.     for(size_t i = 0; i < d.s; ++i) {
     
152.         printf("%f ", d.v[i]);
     
153.     }
     
154.     printf("\n");
     
155. }
     
156. 
     
157. int main(void) {
     
158.     struct data_d_t raw_data = get_input(stdin, 10);
     
159.     qsort(raw_data.v, raw_data.s, sizeof(*raw_data.v), compar_d);
     
160.     struct data_vd_t group_data = get_groups(raw_data, 3);
     
161.     struct data_d_t average = get_average(group_data);
     
162.     print(average);
     
163.     free_d(average);
     
164.     free_vd(group_data);
     
165.     free_d(raw_data);
     
166.     return 0;
     
167. }
     

复制代码

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <math.h>
   
4. 
   
5. int compar_d(const void *a, const void *b) {
   
6.     return *(const double *)a > *(const double *)b;
   
7. }
   
8. 
   
9. void print(double data[], size_t size) {
   
10.     for(size_t i = 0; i < size; ++i) {
    
11.         printf("%f ", data[i]);
    
12.     }
    
13.     printf("\n");
    
14. }
    
15. 
    
16. int main(void) {
    
17.     double raw_buff[10];
    
18.     for(size_t i = 0; i < 10; ++i) {
    
19.         scanf("%lf", &raw_buff[i]);
    
20.     }
    
21.     qsort(raw_buff, 10, sizeof(*raw_buff), compar_d);
    
22.     size_t group_buff[2];
    
23.     //size_t group_size = get_groups(group_buff, raw_buff, 10);
    
24.     {
    
25.         double distance_buff[9];
    
26.         for(size_t i = 0; i < 9; ++i) {
    
27.             distance_buff[i] = fabs(raw_buff[i] - raw_buff[i + 1]);
    
28.         }
    
29.         for(size_t i = 0; i < 2; ++i) {
    
30.             size_t max_index = 0;
    
31.             for(size_t j = 1; j < 9; ++j) {
    
32.                 if(distance_buff[max_index] < distance_buff[j]) {
    
33.                     max_index = j;
    
34.                 }
    
35.             }
    
36.             distance_buff[max_index] = 0;
    
37.             group_buff[i] = max_index;
    
38.         }
    
39.         if(group_buff[0] > group_buff[1]) {
    
40.             size_t tmp = group_buff[0];
    
41.             group_buff[0] = group_buff[1];
    
42.             group_buff[1] = tmp;
    
43.         }
    
44.     }
    
45.     double average_buff[3];
    
46.     //size_t average_size = get_average(average_buff, raw_buff, group_buff, group_size);
    
47.     {
    
48.         {
    
49.             double sum = 0;
    
50.             for(size_t i = 0; i <= group_buff[0]; ++i) {
    
51.                 sum += raw_buff[i];
    
52.             }
    
53.             average_buff[0] = sum / (group_buff[0] + 1);
    
54.         }
    
55.         {
    
56.             double sum = 0;
    
57.             for(size_t i = group_buff[0] + 1; i <= group_buff[1]; ++i) {
    
58.                 sum += raw_buff[i];
    
59.             }
    
60.             average_buff[1] = sum / (group_buff[1] - group_buff[0]);
    
61.         }
    
62.         {
    
63.             double sum = 0;
    
64.             for(size_t i = group_buff[1] + 1; i <= 9; ++i) {
    
65.                 sum += raw_buff[i];
    
66.             }
    
67.             average_buff[2] = sum / (9 - group_buff[1]);
    
68.         }
    
69.     }
    
70.     print(average_buff, 3);
    
71.     return 0;
    
72. }
    

复制代码

魔轩

人造人 发表于 2021-4-7 15:15
一共3个版本

谢谢