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

Текущее решение (проблема с 8 тестом)
Код: 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.
#include <stdio.h>
#include <stdlib.h>

int count_op(int z, int s)
{
	if (z == s) return 0;
	div_t d = div(z, s);
	if (z==0 || s==0 || d.rem != 0 || z / s < 0) return -1;
	int t = 0;
	while (d.quot == 0){
		d.quot /= 2;
		t += 1;
	}
	int delta = (d.quot == 1) ? 1 : 0;
	return t * 2 + d.quot - delta;
}


int main()
{
	int z, s;
	FILE* in = freopen("input.txt", "r", stdin);
	scanf("%i %i", &s, &z);
	fclose(in);
	FILE* out = freopen("output.txt", "w", stdout);
	printf("%i", count_op(z, s));
	fclose(out);
	return 0;
}




PS
Данная тема скорее относится к разделу Программирование, но в связи очередной недавней дискриминацией самого себя (подраздела Программирования) , больше не хочу задавать вопросов в том разделе. С другой стороны, я не сторонник строгой дифференциации, тем более, инструментом решения данной конкретной задачи является семейство языков С/С++
...
Рейтинг: 0 / 0
25.03.2015, 09:26
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38915986
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
С проверками разберись. Сначала на ноль делишь, а потом проверяешь что s==0

Про div() тут как-раз прекрасный пример что не надо читаемостью жертвовать.
Написал бы вместо него
Код: plaintext
1.
quot = z / s;


не накосячил бы с делением на ноль.

Это бесконечный цикл
Код: plaintext
1.
2.
3.
4.
	while (d.quot == 0){
		d.quot /= 2;
		t += 1;
	}
...
Рейтинг: 0 / 0
25.03.2015, 09:59
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916011
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Раз уж ты за супер-мега оптимизаторство борешься, то
Код: plaintext
1.
t += 1;


и
Код: plaintext
1.
t++;


это разные операции для процессора. Есть отдельная команда процессора ( INC ) для увеличения на 1, она быстрее чем сложение ( ADD ), и сложение требует отдельного хранения второго слагаемого.
...
Рейтинг: 0 / 0
25.03.2015, 10:11
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916020
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
По первому замечанию согласен, рефакторинг

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
int count_op(int z, int s)
{
	if (z == s)	return 0;
	if (z == 0 || s == 0)
exit:
	return -1;
	div_t d = div(z, s);
	if (d.rem != 0 || d.quot < 0) goto exit;

	int t = 0;
	while (d.quot == 0){
		d.quot /= 2;
		++t;
	}
	int delta = (d.quot == 1) ? 1 : 0;
	return t * 2 + d.quot - delta;
}



Бесконечного цикла, как мне кажется, быть не должно.. Может что-то не учёл, но такой контрпример не могу подобрать
...
Рейтинг: 0 / 0
25.03.2015, 10:18
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916021
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dima TЕсть отдельная команда процессора ( INC ) для увеличения на 1, она быстрее чем сложение ( ADD ), и сложение требует отдельного хранения второго слагаемого.
Я думаю, что и в этом случае компилятор умнее программиста и выберет то что быстрее ))
...
Рейтинг: 0 / 0
25.03.2015, 10:18
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916022
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Дмитрий, просто

Код: plaintext
1.
t+=1;



смотрится красивее чем унарный инкремент :)
Но я исправил
...
Рейтинг: 0 / 0
25.03.2015, 10:20
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916023
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercury,

За goto внутрь if надо отрывать руки.
Не говоря уже о том, что goto тут нафиг не нужен.
...
Рейтинг: 0 / 0
25.03.2015, 10:21
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916030
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly MoskovskySashaMercury,

За goto внутрь if надо отрывать руки.
Не говоря уже о том, что goto тут нафиг не нужен.

Дело в том, что вы конечно в чём то правы, но мне захотелось посмотреть как будет выглядеть код с goto :) Например, недавно я увидел код Дмитрия следующего вида
Код: plaintext
1.
2.
3.
	while (smth){
		smth do;
	}



И хотя ранее, я никогда не использовал такую стилистику в своём коде, мне понравилось, потому что я увидел как это выглядит. А теперь использую. Вот и сейчас захотел посмотреть :)
...
Рейтинг: 0 / 0
25.03.2015, 10:26
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916031
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Anatoly MoskovskyЯ думаю, что и в этом случае компилятор умнее программиста и выберет то что быстрее ))
Чего тут думать, проверить просто:
Код: plaintext
1.
2.
3.
4.
5.
	int x = GetTickCount();
0040100C  call        dword ptr [__imp__GetTickCount@0 (40A000h)] 
00401012  mov         esi,eax 
	x+=1;
00401014  add         esi,1


MS VC 2008 Express. Сборка Release c дефолтными настройками оптимизации

Не особо умный :)
...
Рейтинг: 0 / 0
25.03.2015, 10:27
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916053
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dima T,

В Express ограничен уровень оптимизаций, так что этот пример ни о чем не говорит.
А например gcc генерит одинаковый код для +=1 и ++.
...
Рейтинг: 0 / 0
25.03.2015, 10:36
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916055
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercury
Код: plaintext
1.
2.
3.
4.
5.
	if (z == 0 || s == 0)
exit:
	return -1;
	div_t d = div(z, s);
	if (d.rem != 0 || d.quot < 0) goto exit;



вместо goto exit рука не поднялась написать return -1?
Забудь про goto, особенно в таком извращенном применении.

SashaMercuryБесконечного цикла, как мне кажется, быть не должно..
А если подумать головой? Не буду подсказывать, сам догадайся.
...
Рейтинг: 0 / 0
25.03.2015, 10:36
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916063
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryмне понравилось, потому что я увидел как это выглядит. А теперь использую.
Ну кому-то и бухать и колоться нравится. Но это не повод ))
...
Рейтинг: 0 / 0
25.03.2015, 10:39
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916073
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Глупый вопрос - чему будет равно t на выходе из
Код: plaintext
1.
while (d.quot == 0){...

если d.quot перед входом в цикл =0?
 
И с какой стати этому циклу вообще завершаться?
...
Рейтинг: 0 / 0
25.03.2015, 10:42
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916079
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercury,

goto можно применять только если в функции есть нетривиальный завершающий код, который надо вызывать из разных веток кода.
Все остальные варианты goto - бессмысленны и вредны.
Схема использования такая:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
int func()
{
    init();
    maincode();
    if (error) goto error:
    maincode();    
    cleanup();
    return 0;
    
error:    
    cleanup();
    return -1;
}
...
Рейтинг: 0 / 0
25.03.2015, 10:44
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916094
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Anatoly MoskovskyDima T,

В Express ограничен уровень оптимизаций, так что этот пример ни о чем не говорит.
А например gcc генерит одинаковый код для +=1 и ++.
Говорит что все компиляторы разные. Полной версии MS VC нет чтобы сравнить. Хотя тот же экспрес оптимизирует такую конструкцию
Код: plaintext
1.
2.
3.
4.
5.
6.
	int x = 1;
	x+=1;
	printf("%d\n", x);
0040100B  push        2    
0040100D  push        offset string "%d\n" (40B3C4h) 
00401012  call        printf (401038h)



И вообще не оптимизирует div()
Код: plaintext
1.
2.
3.
4.
div_t d = div(4, 2);
0040100B  push        2    
0040100D  push        4    
0040100F  call        div (401041h)


Саш, div() это тормоз, по крайней мере в MSVC Express
...
Рейтинг: 0 / 0
25.03.2015, 10:49
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916214
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryНапример, недавно я увидел код Дмитрия следующего вида
Код: plaintext
1.
2.
3.
	while (smth){
		smth do;
	}



И хотя ранее, я никогда не использовал такую стилистику в своём коде, мне понравилось, потому что я увидел как это выглядит. А теперь использую. Вот и сейчас захотел посмотреть :)
Это основы. Причем любого языка, а не только С. Три вида циклов: for(), while() и do ... while()
Если плохо понимаешь как они работают - потрать время на изучение.

while() работает так
Код: plaintext
1.
2.
3.
4.
5.
6.
:while
if(d.quot == 0){
	d.quot /= 2;
	t += 1;
	goto while;
}


SashaMercuryБесконечного цикла, как мне кажется, быть не должно.. Может что-то не учёл, но такой контрпример не могу подобрать
Весь код не посмотрел сразу, в твоем случае не зациклится потому что цикл никогда не выполнится, т.к. все варианты где d.quot == 0 у тебя отсекают предварительные проверки. Т.е. ты написал ненужный кусок кода. Тоже косяк, т.к. зачем-то ты его писал.

PS В суть алгоритма не вдумывался, просто указал на очевидные ошибки.
...
Рейтинг: 0 / 0
25.03.2015, 11:59
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916232
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
Anatoly MoskovskyЗа goto внутрь if надо отрывать руки.каждый начинающий программист должен понаступать на все старые грабли, они ведь так удобно лежат
...
Рейтинг: 0 / 0
25.03.2015, 12:04
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916250
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
Dima TЭто бесконечный цикл
Код: plaintext
1.
2.
3.
4.
	while (d.quot == 0){
		d.quot /= 2;
		t += 1;
	}

с чего бы? d.quot целое ведь.

а вот эта конструкция бессмыссленна:
Код: plaintext
1.
int delta = (d.quot == 1) ? 1 : 0;

ведь только что мы добились того, чтобы d.quot стало равным 0, оно никогда не сможет стать равным 1 )))
...
Рейтинг: 0 / 0
25.03.2015, 12:11
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916300
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
egorychс чего бы? d.quot целое ведь.
0 / 2 сколько будет?
...
Рейтинг: 0 / 0
25.03.2015, 12:29
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916302
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SashaMercuryкак бы её решали на языке С++ или С.
Я бы сначала проверил и отсёк краевые условия:
Код: sql
1.
2.
3.
4.
if (x==y) return 0;
if (x>0 && y<0) return -1;
if (x<0 && y>0) return -1;
if (y%x != 0) return -1;



Потом я бы воспользовался следующим алгоритмом:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
static int primaries[] = {2,3,5,7,...};

result = 0;
for (int i = 0; i<sizeof(primaries)/sizeof(int) && primaries[i]<sqrt(y); ++i)
{
   if (y%primaries[i] == 0)
   {
     y /= primaries[i];
     if (x%primaries[i] == 0)
       x /= primaries[i];
     else
       result += primaries[i];
     if (y == 1)
       return result;
   }
   return -1;
}


Тебе, как математику, должно быть очевидно как он работает.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
25.03.2015, 12:31
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916318
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
Dima Tegorychс чего бы? d.quot целое ведь.
0 / 2 сколько будет?нормально я затупил, качественно прошу прощения
...
Рейтинг: 0 / 0
25.03.2015, 12:42
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916434
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
А по здравому размышлению алгоритм сводится к следующему?
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
if (x==y) return 0;
if (x>0 && y<0) return -1;
if (x<0 && y>0) return -1;

int a = y/x;
int b = y%x;
if (b != 0) return -1;

static int primaries[] = {2,3,5,7,...};

result = 0;
for (int i = 0; i<sizeof(primaries)/sizeof(int) && primaries[i]<sqrt(a); ++i)
{
   if (a%primaries[i] == 0)
   {
     a /= primaries[i];
     result += primaries[i];
     if (a == 1)
       return result;
   }
}
return -1;
...
Рейтинг: 0 / 0
25.03.2015, 13:48
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916773
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ммм.... primes... вкуснятина.
...
Рейтинг: 0 / 0
25.03.2015, 16:50
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916816
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
maytonprimes... вкуснятина.
А без них в одну секунду не уложиться на верхнем конце диапазона.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
25.03.2015, 17:32
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916842
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.
	if(x == y) return 0;
	if(x == 0 || y % x != 0) return -1;
	int a = y/x;
	if (a <= 0) return -1;

	static int primaries[] = {2,3,5,7 ... до 10^9};

	int result = 0;
	int i = 0;
	while(a > 1) {
		if(a % primaries[i] == 0) {
			a /= primaries[i];
			result += primaries[i];
			i = 0;
		} else {
			i++;
			if(i >= sizeof(primaries)/sizeof(int)) return -2; // таблица primeries маленькая
		}
	}
	return result;

...
Рейтинг: 0 / 0
25.03.2015, 17:49
| Ответить | Цитировать | Написать  
25 сообщений из 76, страница 1 из 4
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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