ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение задачи на языке программирования Си
25 сообщений из 26, страница 1 из 2
  1  все
Решение задачи на языке программирования Си
    #38878200
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Здравствуйте.
Разминался, решал несложную задачу .
На одном из тестов задача валится, и не могу понять почему.

Привожу интуитивно понятный код. Если вы предложите оптимальный алгоритм, было бы здорово. А может быть найдете ошибку. Подскажите пожалуйста

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>



struct Range
{
	long double s;
	long double e;
};

void viewRange(struct Range* r)
{
	printf("Range s = %f\nRange e = %f\n", r->s, r->e);
}

void rangeEstimate_inplace(struct Range* r, long double x) //расчёт диапазона происходит из погрешости 0.1
{
	r->s = x / 1.1;
	r->e = x / 0.9;
}

void intersectionRanges_inplace(struct Range* r1, const struct Range* r2)
{
	r1->s = (r1->s >= r2->s) ? r1->s : r2->s;
	r1->e = (r1->e <= r2->e) ? r1->e : r2->e;
}



int main()
{
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int k; fscanf(in, "%i", &k); //count signals
	
	for (int i = 0; i < k; ++i)//reading each signal MAIN LOOP
	{
		int n; fscanf(in, "%i", &n); //length of sequence

		int flag = 0;
		char* res = (char*)malloc(sizeof(char)*(5 * n + 1));
		char* cur_res = res;

		int t;  fscanf(in, "%i", &t);

		struct Range* range = (struct Range*)malloc(sizeof(struct Range));
		rangeEstimate_inplace(range,(long double)t); //start value
		*cur_res++ = 1;
		struct Range* cur = (struct Range*)malloc(sizeof(struct Range));

		int counter = 1;
		for (int j = 1; j < n; ++j)
		{
			int x; fscanf(in, "%i", &x); 
			if (abs(long double(t - x)) < abs(long double(2 * t - x)))//один бит  
			{
				rangeEstimate_inplace(cur, (long double)x);
				*cur_res++ = 1 - j % 2;
				counter += 1;
			}
			else//два бита
			{
				rangeEstimate_inplace(cur, ((long double)x) / (long double)2.0);
				*cur_res++ = 1 - j % 2;
				*cur_res++ = 1 - j % 2;
				counter += 2;
			}
			intersectionRanges_inplace(range, cur);
			if (range->s > range->e)
			{
				flag = 1;
				break;
			}
		}
		
		cur_res = res;
		for (int i = 0; i < counter; i += 2)
		{
			char t1 = *(res + i);
			char t2 = *(res + i + 1);
			if (t1 == 0 && t2 == 1)
			{
				*cur_res++ = '0';
			}
			else if (t1 == 1 && t2 == 0)
			{
				*cur_res++ = '1';
			}
			else
			{
				flag = 1;
				break;
			}
		}
		*cur_res = '\0';

		if (flag || counter % 2 != 0 || n % 2 != 1) //|| *(cur_res - 1) != '0'
		{
			fprintf(out, "ERROR\n");
		}
		else
		{
			fprintf(out, "%s\n", res);
		}
				
		free(res); 
		free(range);
		free(cur);
	}
	fclose(in);
	fclose(out);
	return 0;
}
...
Рейтинг: 0 / 0
12.02.2015, 15:32
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878352
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Как-то все сложно у тебя.

 
Поизучай мой вариант
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
#define POS_END		0
#define POS_CENTER	1

void f(int* sig)
{
	int cnt = *sig;
	sig++;
	// допуски полупериода
	int half_period_min = *sig * 90 / 100;
	int half_period_max = *sig * 110 / 100;
	printf("half period beween %d %d\n", half_period_min, half_period_max);
	// допуски периода
	int period_min = *sig * 2 * 80 / 100;
	int period_max = *sig * 2 * 120 / 100;
	printf("period beween %d %d\n", period_min, period_max);
	// текущее значение
	int cur = 1;
	// текущее положение
	int pos = POS_END;
	for(;cnt > 0; cnt--, sig++) {
		//printf("%d\n", *sig);
		if(*sig >= half_period_min && *sig <= half_period_max) {
			// пройдено полпериода
			pos = 1 - pos;
		} else if(*sig >= period_min && *sig <= period_max) {
			// пройден период
			cur = 1 - cur;
		} else {
			// выход за пределы погрешности
			printf("ERROR\n");
			break;
		}
		if(pos == POS_CENTER) {
			//вывод очередного бита
			printf("%d", cur);
		}
	}
	printf("\n");
}

int main()
{
	int src1[] = {5,42,43,39,93,44};
	int src2[] = {5,10,10,22,10,30};
	f(src1);
	f(src2);
	system("pause");
	return 0;
}



Алгоритм не буду расписывать, попробуй сам догадаться
...
Рейтинг: 0 / 0
12.02.2015, 17:03
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878646
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Здравствуйте.
Дмитрий, в связи с выводом немного изменил ваш алгоритм. Валится на втором тесте. Мой код на 13 тесте
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
// 657_by_Dima_T.cpp : Defines the entry point for the console application.
//

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

#define POS_END		0
#define POS_CENTER	1

void f(int* res, int* sig, FILE* out)
{
	int cnt = *sig;
	sig++;
	// допуски полупериода
	int half_period_min = *sig * 90 / 100;
	int half_period_max = *sig * 110 / 100;
	printf("half period beween %d %d\n", half_period_min, half_period_max);
	// допуски периода
	int period_min = *sig * 2 * 80 / 100;
	int period_max = *sig * 2 * 120 / 100;
	//printf("period beween %d %d\n", period_min, period_max);
	// текущее значение
	int cur = 1;
	// текущее положение
	int pos = POS_END;

	int count = 0;
	int flag = 0;

	for (; cnt > 0; cnt--, sig++) 
	{
		//printf("%d\n", *sig);
		if (*sig >= half_period_min && *sig <= half_period_max) {
			// пройдено полпериода
			pos = 1 - pos;
		}
		else if (*sig >= period_min && *sig <= period_max) {
			// пройден период
			cur = 1 - cur;
		}
		else {
			// выход за пределы погрешности
			flag = 1;
			break;
		}
		if (pos == POS_CENTER) {
			//вывод очередного бита
			res[count++] = cur;
		}
	}
	if (!flag)
	{
		for (int i = 0; i < count; ++i)
		{
			fprintf(out, "%i", res[i]);
		}
	}
	else
	{
		fprintf(out, "ERROR");
	}
	fprintf(out,"\n");
}


int main()
{
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int k; fscanf(in, "%i", &k); //count signals

	int* res = (int*)malloc(sizeof(int) * 50000);

	for (int i = 0; i < k; ++i)//reading each signal MAIN LOOP
	{
		int n; fscanf(in, "%i", &n); //length of curren sequence
		int* ar = (int*)malloc(sizeof(int)*(n + 1));
		*ar = n;
		for (int i = 1; i < n+1; ++i)
			fscanf(in, "%i", ar + i);
		f(res, ar, out);
		free(ar);
	}
	free(res);
	fclose(in);
	fclose(out);
	return 0;
}
...
Рейтинг: 0 / 0
13.02.2015, 02:19
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878647
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Дмитрий, мне кажется что ваш алгоритм неверный. Вы оптимизировали вывод ( но в случае вывода ERROR этот вывод будет некорректным, потому я переделал немного ваш вывод). Проверка допустимого диапазона у вас осуществляется только один раз.

Мой алгоритм основан на пересечение допустимых диапазонов. Допустимый диапазон постоянно сужается
...
Рейтинг: 0 / 0
13.02.2015, 02:35
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878710
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДмитрий, в связи с выводом немного изменил ваш алгоритм. Валится на втором тесте.
Наверно из-за проверки диапазонов.
Добавил первым проходом расчет диапазонов и проверку на допустимость
 
исходник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#pragma warning(disable: 4996) // fopen(), strcpy()

#define POS_END		0
#define POS_CENTER	1

void f(char* res, int* sig)
{
	int* end = sig + *sig + 1;
	sig++;
	// расчет интервалов 
	int half_period_min = *sig;
	int half_period_max = *sig;
	int period_min = *sig * 2;
	int period_max = *sig * 2;
	int border = *sig * 3 / 2;
	for(int* i = sig; i < end; i++) {
		if(*i > border) {
			if(period_min > *i) period_min = *i;
			if(period_max < *i) period_max = *i;
		} else {
			if(half_period_min > *i) half_period_min = *i;
			if(half_period_max < *i) half_period_max = *i;
		}
	}
#ifdef _DEBUG
	printf("half period beween %d %d delta %f\n", half_period_min, half_period_max, (double)(half_period_max - half_period_min) / ((half_period_max + half_period_min) / 2));
	printf("period beween %d %d delta %f\n", period_min, period_max, (double)(period_max - period_min) / ((period_max + period_min) / 2));
#endif

	// проверка допустимых отклонений (переделать)
	if((double)(half_period_max - half_period_min) / ((half_period_max + half_period_min) / 2) > 0.2
		|| (double)(period_max - period_min) / ((period_max + period_min) / 2) > 0.2) {
			strcpy(res, "ERROR");
	} else {
		char cur = '1'; // текущее значение
		int pos = POS_END; // текущее положение
		for(; sig < end; sig++) {
			if (*sig > border) {
				// пройден период
				cur ^= 1;
			} else {
				// пройдено полпериода
				pos ^= 1;
			}
			if (pos == POS_CENTER) {
				//вывод очередного бита
				*res = cur;
				res++;
			}
		}
		*res = 0;
	}
}

int main()
{
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int k; 
	fscanf(in, "%i", &k); //count signals

	for (int i = 0; i < k; ++i)//reading each signal MAIN LOOP
	{
		int n; 
		fscanf(in, "%i", &n); //length of curren sequence
		int* ar = (int*)malloc(sizeof(int)*(n + 1));
		*ar = n;
		for (int i = 1; i < n+1; ++i) {
			fscanf(in, "%i", ar + i);
		}
		char* res = (char*) malloc(sizeof(char)*(n + 1));
		f(res, ar);
#ifdef _DEBUG
		puts(res);
#else
		fputs(res, out);
#endif
		free(ar);
		free(res);
	}
	fclose(in);
	fclose(out);
#ifdef _DEBUG
	system("pause");
#endif
	return 0;
}


Принцип такой: т.к. длинный и короткий промежутки отличаются вдвое, а допуск 10%, то считаем что любой короткий * 1,5 не попадает в диапазон длинных, поэтому берем границу первый короткий * 1,5 - все что ниже короткие, выше - длинные.

Дальше проверка полученных мин/макс. на допустимость отклонений.
Правда тут я немного не доделал, отдельно короткие проверяю, отдельно длинные. В идеале их как-то надо совместить, т.к. реально период один. Не соображу как.
Т.е. надо проверить существования какого-то Х, т.е. периода, удовлетворяющего условиям
X / 2 * 0.9 > half_period_min
X / 2 * 1.1 < half_period_max
X * 0.9 > period_min
X * 1.1 < period_max

Подумай, может придумаешь как допилить эту проверку.

PS Прячь большие исходники под спойлер, а то среди этих простыней текст заметить сложно.
...
Рейтинг: 0 / 0
13.02.2015, 09:07
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878741
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Косяк заметил в расчете мин/макс.
 
поправленный исходник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#pragma warning(disable: 4996) // fopen(), strcpy()

#define POS_END		0
#define POS_CENTER	1

void f(char* res, int* sig)
{
	int* end = sig + *sig + 1;
	sig++;
	// расчет интервалов 
	int half_period_min = *sig;
	int half_period_max = *sig;
	int period_min = 0;
	int period_max = 0;
	int border = *sig * 3 / 2;
	for(int* i = sig; i < end; i++) {
		if(*i > border) {
			if(period_min == 0 || period_min > *i) period_min = *i;
			if(period_max < *i) period_max = *i;
		} else {
			if(half_period_min > *i) half_period_min = *i;
			if(half_period_max < *i) half_period_max = *i;
		}
	}
#ifdef _DEBUG
	printf("half period beween %d %d delta %f\n", half_period_min, half_period_max, (double)(half_period_max - half_period_min) / ((half_period_max + half_period_min) / 2));
	printf("period beween %d %d delta %f\n", period_min, period_max, (double)(period_max - period_min) / ((period_max + period_min) / 2));
#endif

	// проверка допустимых отклонений
	if((double)(half_period_max - half_period_min) / ((half_period_max + half_period_min) / 2) > 0.2
		|| (period_min != 0 && (double)(period_max - period_min) / ((period_max + period_min) / 2)) > 0.2) {
			strcpy(res, "ERROR");
	} else {
		char cur = '1'; // текущее значение
		int pos = POS_END; // текущее положение
		for(; sig < end; sig++) {
			if (*sig > border) {
				// пройден период
				cur ^= 1;
			} else {
				// пройдено полпериода
				pos ^= 1;
			}
			if (pos == POS_CENTER) {
				//вывод очередного бита
				*res = cur;
				res++;
			}
		}
		*res = 0;
	}
}

int main()
{
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int k; 
	fscanf(in, "%i", &k); //count signals

	for (int i = 0; i < k; ++i)//reading each signal MAIN LOOP
	{
		int n; 
		fscanf(in, "%i", &n); //length of curren sequence
		int* ar = (int*)malloc(sizeof(int)*(n + 1));
		*ar = n;
		for (int i = 1; i < n+1; ++i) {
			fscanf(in, "%i", ar + i);
		}
		char* res = (char*) malloc(sizeof(char)*(n + 1));
		f(res, ar);
#ifdef _DEBUG
		puts(res);
#endif
		fputs(res, out);
		free(ar);
		free(res);
	}
	fclose(in);
	fclose(out);
#ifdef _DEBUG
	system("pause");
#endif
	return 0;
}



PS В попытках порешать уравнение на допустимость сломал мозг. Математика напрочь забыта
...
Рейтинг: 0 / 0
13.02.2015, 09:41
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878742
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Да, это так. Либо длинный, либо короткий отрезок. Если короткий не подходит, то длинный делим на два и проверяем на соответствие 10 % погрешности. У меня сделано так
...
Рейтинг: 0 / 0
13.02.2015, 09:41
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878746
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Поправленный исходник вновь валится на 2 тесте (
...
Рейтинг: 0 / 0
13.02.2015, 09:44
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878749
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Вот так у меня в коде

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
if (abs(long double(t - x)) < abs(long double(2 * t - x)))//один бит  
			{
				rangeEstimate_inplace(cur, (long double)x);
				*cur_res++ = 1 - j % 2;
				counter += 1;
			}
			else//два бита
			{
				rangeEstimate_inplace(cur, ((long double)x) / (long double)2.0);
				*cur_res++ = 1 - j % 2;
				*cur_res++ = 1 - j % 2;
				counter += 2;
			}



Вы не изменяете диапазон, верно ?
...
Рейтинг: 0 / 0
13.02.2015, 09:46
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878761
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryПоправленный исходник вновь валится на 2 тесте (
Нашел косяк. Надо еще корректность последовательности проверять. В середине всегда должен быть перепад.
 
Проверяй
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#pragma warning(disable: 4996) // fopen(), strcpy()

#define POS_END		0
#define POS_CENTER	1

void f(char* res, int* sig)
{
	int* end = sig + *sig + 1;
	sig++;
	// расчет интервалов 
	int half_period_min = *sig;
	int half_period_max = *sig;
	int period_min = 0;
	int period_max = 0;
	int border = *sig * 3 / 2;
	for(int* i = sig; i < end; i++) {
		if(*i > border) {
			if(period_min == 0 || period_min > *i) period_min = *i;
			if(period_max < *i) period_max = *i;
		} else {
			if(half_period_min > *i) half_period_min = *i;
			if(half_period_max < *i) half_period_max = *i;
		}
	}
#ifdef _DEBUG
	printf("half period beween %d %d delta %f\n", half_period_min, half_period_max, (double)(half_period_max - half_period_min) / ((half_period_max + half_period_min) / 2));
	printf("period beween %d %d delta %f\n", period_min, period_max, (double)(period_max - period_min) / ((period_max + period_min) / 2));
#endif

	// проверка допустимых отклонений
	if((double)(half_period_max - half_period_min) / ((half_period_max + half_period_min) / 2) > 0.2
		|| (period_min != 0 && (double)(period_max - period_min) / ((period_max + period_min) / 2)) > 0.2) {
			strcpy(res, "ERROR");
	} else {
		char cur = '1'; // текущее значение
		int pos = POS_END; // текущее положение
		char* p = res;
		for(; sig < end; sig++) {
			if (*sig > border) {
				// пройден период
				if(pos == POS_END) {
					// не было перепада в центре
					strcpy(res, "ERROR");
					p = NULL;
					break;
				}
				cur ^= 1;
			} else {
				// пройдено полпериода
				pos ^= 1;
			}
			if (pos == POS_CENTER) {
				//вывод очередного бита
				*p = cur;
				p++;
			}
		}
		if(p) *p = 0;
	}
}

int main()
{
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int k; 
	fscanf(in, "%i", &k); //count signals

	for (int i = 0; i < k; ++i)//reading each signal MAIN LOOP
	{
		int n; 
		fscanf(in, "%i", &n); //length of curren sequence
		int* ar = (int*)malloc(sizeof(int)*(n + 1));
		*ar = n;
		for (int i = 1; i < n+1; ++i) {
			fscanf(in, "%i", ar + i);
		}
		char* res = (char*) malloc(sizeof(char)*((n > 5 ? n : 5) + 1));
		f(res, ar);
#ifdef _DEBUG
		puts(res);
#endif
		fputs(res, out);
		free(ar);
		free(res);
	}
	fclose(in);
	fclose(out);
#ifdef _DEBUG
	system("pause");
#endif
	return 0;
}

...
Рейтинг: 0 / 0
13.02.2015, 09:59
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878767
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryВы не изменяете диапазон, верно ?
По условию время передачи одного бита константа. Зачем его динамически подбирать? Я просто нахожу мин/макс значения и проверяю разброс на соответствие допустимой погрешности, правда проверка не совсем верная. См. выше.
...
Рейтинг: 0 / 0
13.02.2015, 10:04
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878769
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
2 тест, валится. На каждом сигнале нужно производить пересечение допустимых интервалов..
...
Рейтинг: 0 / 0
13.02.2015, 10:05
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878774
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryВы не изменяете диапазон, верно ?
По условию время передачи одного бита константа. Зачем его динамически подбирать? Я просто нахожу мин/макс значения и проверяю разброс на соответствие допустимой погрешности, правда проверка не совсем верная. См. выше.

Пусть A имеет диапазон [x0;x1], B [x1;x2], C[y;x0]

Совместна ли эта система ? Судя по вашему алгоритму да, но это не так
...
Рейтинг: 0 / 0
13.02.2015, 10:07
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878788
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercury2 тест, валится. На каждом сигнале нужно производить пересечение допустимых интервалов..
Валится с проверкой последовательности:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
				// пройден период
				if(pos == POS_END) {
					// не было перепада в центре
					strcpy(res, "ERROR");
					p = NULL;
					break;
				}


?
там исходные данные не показывают на которых валится? :)
SashaMercuryНа каждом сигнале нужно производить пересечение допустимых интервалов..
там написано так:
ТЗреальное время , в течение которого луч находился в постоянном состоянии ( – вещественное число), и зафиксированное прибором время ( – целое число) удовлетворяют неравенству (L - L') / L ≤ 0.1 .
L это T или T/2, т.е. константа т.к. T константа. Следовательно проверить мин/макс достаточно.
Тут еще добавляется погрешность преобразования вещественное в целое, это я не учел при проверке. Общая погрешность может быть > 0.1
...
Рейтинг: 0 / 0
13.02.2015, 10:22
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38878799
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryПусть A имеет диапазон [x0;x1], B [x1;x2], C[y;x0]

Совместна ли эта система ? Судя по вашему алгоритму да, но это не так
Не умничай, на простых примерах напиши.
Уже писал что математика забыта :)

Придумай как проверить существeет ли X удовлетворяющий условию
X / 2 * 0.9 > half_period_min
X / 2 * 1.1 < half_period_max
X * 0.9 > period_min
X * 1.1 < period_max

Мне только подбор в голову приходит.

Надо доделывать проверку. Вот последовательность на которой моя недоделанная проверка интервалов не срабатывает
Код: plaintext
1.
2.
3.
4.
5.
6.
5
42
43
39
193
44
...
Рейтинг: 0 / 0
13.02.2015, 10:34
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879015
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Вспомнил математику :)

Свел диапазоны к одному знаменателю. Смысл такой: считаем что полученные мин/макс значения имеют максимальную погрешность, обратным счетом получаем точки отсчета, далее проверка что все максимумы больше всех минимумов. Т.е. есть непустой диапазон в котором находится период.

 
Исходник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#pragma warning(disable: 4996) // fopen(), strcpy()

#define POS_END		0
#define POS_CENTER	1

void f(char* res, int* sig)
{
	int* end = sig + *sig + 1;
	sig++;
	// расчет интервалов 
	int half_period_min = *sig;
	int half_period_max = *sig;
	int period_min = 0;
	int period_max = 0;
	int border = *sig * 3 / 2;
	for(int* i = sig; i < end; i++) {
		if(*i > border) {
			if(period_min == 0 || period_min > *i) period_min = *i;
			if(period_max < *i) period_max = *i;
		} else {
			if(half_period_min > *i) half_period_min = *i;
			if(half_period_max < *i) half_period_max = *i;
		}
	}
	if(period_min == 0) { // не было длинных интервалов
		// берем два средних чтобы далее 0 не мешал
		period_min = half_period_max + half_period_min;
		period_max = period_min;
	}
	// предельные значения периода из предположения что мин/макс крайние значения
	double half_limit_max = (double) half_period_min * 2 / 0.9;
	double half_limit_min = (double) half_period_max * 2 / 1.1;
	double limit_max = (double) period_min / 0.9;
	double limit_min = (double) period_max / 1.1;
#ifdef _DEBUG
	for(int* i = sig; i < end; i++) printf("%d ", *i);
	printf("\nhalf period beween (%d - %d) limit (%f - %f)", half_period_min, half_period_max, half_limit_min, half_limit_max);
	printf("\nperiod beween (%d - %d) limit (%f - %f)\n", period_min, period_max, limit_min, limit_max);
#endif

	// проверка допустимых отклонений
	if(half_limit_max < half_limit_min 
		|| limit_max < limit_min
		|| half_limit_max < limit_min
		|| limit_max < half_limit_min) {
			strcpy(res, "ERROR");
	} else {
		char cur = '1'; // текущее значение
		int pos = POS_END; // текущее положение
		char* p = res;
		for(; sig < end; sig++) {
			if (*sig > border) {
				// пройден период
				if(pos == POS_END) {
					// не было перепада в центре
					strcpy(res, "ERROR");
					p = NULL;
					break;
				}
				cur ^= 1;
			} else {
				// пройдено полпериода
				pos ^= 1;
			}
			if (pos == POS_CENTER) {
				//вывод очередного бита
				*p = cur;
				p++;
			}
		}
		if(p) *p = 0;
	}
}

int main()
{
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int k; 
	fscanf(in, "%i", &k); //count signals

	for (int i = 0; i < k; ++i)//reading each signal MAIN LOOP
	{
		int n; 
		fscanf(in, "%i", &n); //length of curren sequence
		int* ar = (int*)malloc(sizeof(int)*(n + 1));
		*ar = n;
		for (int i = 1; i < n+1; ++i) {
			fscanf(in, "%i", ar + i);
		}
		char* res = (char*) malloc(sizeof(char)*((n > 5 ? n : 5) + 1));
		f(res, ar);
#ifdef _DEBUG
		puts(res);
		puts("");
#endif
		fputs(res, out);
		free(ar);
		free(res);
	}
	fclose(in);
	fclose(out);
#ifdef _DEBUG
	system("pause");
#endif
	return 0;
}



PS При желании все можно сделать в один проход и вообще избавиться от предварительного чтения входных данных, т.е. читать по одному и сразу обрабатывать.
...
Рейтинг: 0 / 0
13.02.2015, 12:39
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879049
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Дмитрий, программа снова не проходит тест 2.. На каких данных не показывает
...
Рейтинг: 0 / 0
13.02.2015, 13:01
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879142
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДмитрий, программа снова не проходит тест 2.. На каких данных не показывает
Сломал весь мозг в догадках что еще не так.
На всякий случай добавил еще проверку обрывов, т.е. то что на середине периода ряд закончился.
Зарегался на том сайте чтоб сюда не постить все мои потуги.

Оказалось все просто: я перевод строки забыл писать в output.txt (fputs() это не делает), все ответы были в строчку

 
Правильный исходник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#pragma warning(disable: 4996) // fopen(), strcpy()

#define POS_END		0
#define POS_CENTER	1

void f(char* res, int* sig)
{
	int* end = sig + *sig + 1;
	sig++;
	// расчет интервалов 
	int half_period_min = *sig;
	int half_period_max = *sig;
	int period_min = 0;
	int period_max = 0;
	int border = *sig * 3 / 2;
	for(int* i = sig; i < end; i++) {
		if(*i > border) {
			if(period_min == 0 || period_min > *i) period_min = *i;
			if(period_max < *i) period_max = *i;
		} else {
			if(half_period_min > *i) half_period_min = *i;
			if(half_period_max < *i) half_period_max = *i;
		}
	}
	if(period_min == 0) { // не было длинных интервалов
		// берем два средних чтобы далее 0 не мешал
		period_min = half_period_max + half_period_min;
		period_max = period_min;
	}
	// предельные значения периода из предположения что мин/макс крайние значения
	double half_limit_max = (double) half_period_min * 2 / 0.9;
	double half_limit_min = (double) half_period_max * 2 / 1.1;
	double limit_max = (double) period_min / 0.9;
	double limit_min = (double) period_max / 1.1;
#ifdef _DEBUG
	for(int* i = sig; i < end; i++) printf("%d ", *i);
	printf("\nhalf period beween (%d - %d) limit (%f - %f)", half_period_min, half_period_max, half_limit_min, half_limit_max);
	printf("\nperiod beween (%d - %d) limit (%f - %f)\n", period_min, period_max, limit_min, limit_max);
#endif

	// проверка допустимых отклонений
	if(half_limit_max < half_limit_min 
		|| limit_max < limit_min
		|| half_limit_max < limit_min
		|| limit_max < half_limit_min) {
			strcpy(res, "ERROR");
	} else {
		char cur = '1'; // текущее значение
		int pos = POS_END; // текущее положение
		char* p = res;
		for(; sig < end; sig++) {
			if (*sig > border) {
				// пройден период
				if(pos == POS_END) {
					// не было перепада в центре
					strcpy(res, "ERROR");
					p = NULL;
					break;
				}
				cur ^= 1;
			} else {
				// пройдено полпериода
				pos ^= 1;
			}
			if (pos == POS_CENTER) {
				//вывод очередного бита
				*p = cur;
				p++;
			}
		}
		if(p) *p = 0;
		if(pos != POS_END) {
			// остановились на середине интервала
			strcpy(res, "ERROR");
		}
	}
}

int main()
{
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int k; 
	fscanf(in, "%i", &k); //count signals

	for (int i = 0; i < k; ++i)//reading each signal MAIN LOOP
	{
		int n; 
		fscanf(in, "%i", &n); //length of curren sequence
		int* ar = (int*)malloc(sizeof(int)*(n + 1));
		*ar = n;
		for (int i = 1; i < n+1; ++i) {
			fscanf(in, "%i", ar + i);
		}
		char* res = (char*) malloc(sizeof(char)*((n > 5 ? n : 5) + 1));
		f(res, ar);
#ifdef _DEBUG
		puts(res);
		puts("");
#endif
		fputs(res, out);
		fputs("\n", out);
		free(ar);
		free(res);
	}
	fclose(in);
	fclose(out);
#ifdef _DEBUG
	system("pause");
#endif
	return 0;
}

...
Рейтинг: 0 / 0
13.02.2015, 14:00
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879645
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Но если все ответы были в строчку, то почему проходил 1 тест ?
...
Рейтинг: 0 / 0
14.02.2015, 07:07
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879646
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Вы уверены что нельзя обойтись одной оценкой ? На полупериод, например
...
Рейтинг: 0 / 0
14.02.2015, 07:26
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879662
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryНо если все ответы были в строчку, то почему проходил 1 тест ?
Наверно там проверка результата по совпадению всех символов ответа без учета "хвоста", т.е. при ответе "110" подходит любой: "110ERROR",
"11012" и т.п.

SashaMercuryВы уверены что нельзя обойтись одной оценкой ? На полупериод, например
Вчера сомневался. Ниже доказательство что можно.

Сообразил как мои уравнения 17259000 склеить (я изначально больше/меньше наоборот написал).
Вот проверка на существование периода длиной X
Код: plaintext
1.
2.
3.
4.
X * 0.9 <= half_period_min * 2
X * 0.9 <= period_min
X * 1.1 >= half_period_max * 2
X * 1.1 >= period_max

преобразуем в
Код: plaintext
1.
X * 0.9 <= MIN(period_min, half_period_min * 2)
X * 1.1 >= MAX(period_max, half_period_max * 2)

выкидываем X и получаем формулу проверки
Код: plaintext
MIN(period_min, half_period_min * 2) / 0.9 >= MAX(period_max, half_period_max * 2) / 1.1

или в общем виде так
Код: plaintext
1.
MIN(min(длинные), min(короткие * 2)) * 1.1 >= MAX(max(длинные), max(короткие * 2)) * 0.9



Т.е. можно сразу привести длинные к коротким или наоборот. Проверь.
...
Рейтинг: 0 / 0
14.02.2015, 10:01
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879720
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Изучай.
 
Версия 2.0.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable: 4996) // fopen(), strcpy()

void main()
{
	FILE* in = fopen("input.txt", "r");
	FILE* out = fopen("output.txt", "w");
	int k; 
	fscanf(in, "%i", &k); //count signals
	while(k--) {
		char res[32768]; // максимум 32767 по условиям
		char* p = res;
		char val = '1'; // текущее значение
		int pos_end = 1; // текущее положение
		int min = 0x7fffffff, max = 0; // мин, макс. периода
		int border = 0; // граница длинных/коротких
		int err = 0; // код ошибки
		int n;
		fscanf(in, "%i", &n);
		while(n--) { // обработка одной последовательности
			int cur;
			fscanf(in, "%i", &cur);
#ifdef _DEBUG
			printf("%d ", cur);
#endif
			if(!border) border = cur * 3 / 2;
			if (cur > border) {
				// полный период
				if(min > cur) min = cur;
				if(max < cur) max = cur;
				if(pos_end) {
					// не было перепада в центре
					err = 1;
				}
				val ^= 1;
			} else {
				// полупериод
				if(min > cur * 2) min = cur * 2;
				if(max < cur * 2) max = cur * 2;
				pos_end ^= 1;
			}
			if (!pos_end) {
				//вывод очередного бита
				*p++ = val;
			}
		}
		*p = 0;
		if(!pos_end) {
			// остановились на середине интервала
			err = 2;
		}
		if(1.1 * min < 0.9 * max) {
			// Выход за допустимые отклонения
			err = 3;
		}
		fprintf(out, "%s\n", err ? "ERROR" : res);
#ifdef _DEBUG
	printf("\nmax = %d  min = %d\n", min, max);
	if(err) {
		printf("ERROR#%d\n\n", err);
	} else {
		printf("res = %s\n\n", res);
	}
#endif
	}
	fclose(in);
	fclose(out);
#ifdef _DEBUG
	system("pause");
#endif
}


Убрал лишнее. Сделал весь расчет в один проход без буферизации ввода.
...
Рейтинг: 0 / 0
14.02.2015, 12:56
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879883
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryВы ....
Оффтоп, но не могу не написать. Мне неприятно когда ко мне обращаются на "вы". Сегодня обращение на "Вы" это в большинстве случаев не проявление уважения, а затуманивание восприятия чтобы в дальнейшем что-то впарить или откровенно кинуть.
Поэтому давай на "ты". Тем более что ты гораздо умнее чем был я в твоем возрасте.

Лично я привык что все тут на "ты", это же форум программистов, тут важно умение, а не возраст.
...
Рейтинг: 0 / 0
14.02.2015, 20:47
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38879896
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Модератор: Одного оффтопика достаточно
...
Рейтинг: 0 / 0
14.02.2015, 21:23
| Ответить | Цитировать | Написать  
Решение задачи на языке программирования Си
    #38880117
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryВы ....
Оффтоп, но не могу не написать. Мне неприятно когда ко мне обращаются на "вы". Сегодня обращение на "Вы" это в большинстве случаев не проявление уважения, а затуманивание восприятия чтобы в дальнейшем что-то впарить или откровенно кинуть.
Поэтому давай на "ты". Тем более что ты гораздо умнее чем был я в твоем возрасте.

Лично я привык что все тут на "ты", это же форум программистов, тут важно умение, а не возраст.

Хорошо C:
PS
нет, не умнее. Завтра разберу твой вариант, и также постараюсь понять в чём у меня ошибка. Спасибо :)
...
Рейтинг: 0 / 0
15.02.2015, 14:45
| Ответить | Цитировать | Написать  
25 сообщений из 26, страница 1 из 2
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение задачи на языке программирования Си
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]