кодесурса
«C

Упражнения C: Найти медиану двух заданных отсортированных массивов, которые не являются пустыми

script1adsense2code
script1adsense3code

Практика программирования C: Упражнение 3 с решением

Напишите программирование на C, чтобы найти медиану двух заданных отсортированных массивов, которые не являются пустыми.

Код C:

#include <stdio.h>
#include <stdlib.h>
static double find_kth(int a[], int a_len, int b[], int b_len, int k)  
{  
    if (a_len > b_len) {
        return find_kth(b, b_len, a, a_len, k);
    }
    if (a_len == 0) {
        return b[k - 1];
    }
    if (k == 1) {
        return a[0] < b[0] ? a[0] : b[0];
    }
    int ia = k / 2 < a_len ? k / 2 : a_len;
    int ib = k - ia;  
    if (a[ia - 1] < b[ib - 1]) {
 
        return find_kth(a + ia, a_len - ia, b, b_len, k - ia);
    } 
	 else if (a[ia - 1] > b[ib - 1]) {  
        return find_kth(a, a_len, b + ib, b_len - ib, k - ib);
    } else {
        return a[ia - 1];
    }
}
static double find_median_sorted_arrays(int* num1, int num1_size, int* num2, int num2_size)
{
    int half = (num1_size + num2_size) / 2;
    if ((num1_size + num2_size) & 0x1) {
        return find_kth(num1, num1_size, num2, num2_size, half + 1);
    } else {
        return (find_kth(num1, num1_size, num2, num2_size, half) + find_kth(num1, num1_size, num2, num2_size, half + 1)) / 2;
    }
}
int main(void)
{
    int num1[] = {1, 2, 5, 6, 7 };
    int num2[] = {10, 14, 19, 35, 45, 50};
    //int num1[] = {1, 3};
    //int num2[] = {2, 4};
   int s1 = sizeof(num1)/sizeof(num1[0]);
    int s2 = sizeof(num2)/sizeof(num2[0]);
    printf("Median of the above two sorted arrays is: %f\n", find_median_sorted_arrays(num1, s1, num2, s2));  
    return 0;
}

Пример вывода:

 Медиана двух вышеупомянутых отсортированных массивов: 10.000000

Блок - схема:

«C

Решение

Внесите свой код и комментарии через Disqus.

Previous: написать программу на C, чтобы найти длину самой длинной подстроки в данной строке без повторяющихся символов.
Далее: Напишите программу на C, чтобы найти самую длинную палиндромную подстроку из данной строки. Максимальная длина данной строки составляет 1000.

Каков уровень сложности этого упражнения?

Новый контент: Composer: менеджер зависимостей для PHP , R программирования


script1adsense4code
script1adsense5code
disqus2code
script1adsense6code
script1adsense7code
script1adsense8code
buysellads2code