Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 [2]  Все   Вниз
  Печать  
Автор Тема: [c++] Простые гири  (Прочитано 27205 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #30 : 26-11-2009 13:30 » 

а почему ты начинаешь считать от максимального числа?
Ни в ТЗ, ни в логике этого не видно. Тебе так захотелось?
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #31 : 26-11-2009 13:50 » 

Хе? Не понял? Ты о чём?

Вводится некое число N (максимум 500 000) - от него я и начинаю считать.

Имеются гири с массами: 1 г, 2 г, ..., N г (N≤500000).

Входные данные
Входной файл INPUT.TXT содержит число N.

В моём примере N=100. Или?
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #32 : 26-11-2009 13:54 » 

N=100
максимальная сумма <= 100+100-2

ты начинаешь перебор гирь от 99. Почему?
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #33 : 26-11-2009 13:56 » 

Ха, прикол. Паскалевская прожка по линку даёт для N=100 49 пар

1  100
2  99
3  98
4  97
5  96
6  95
7  94
8  93
9  92
10  91
11  90
12  89
13  88
14  87
15  86
16  85
17  84
18  83
19  82
20  81
21  80
22  79
23  78
24  77
25  76
26  75
27  74
28  73
29  72
30  71
31  70
32  69
33  68
34  67
35  66
36  65
37  64
38  63
39  62
40  61
41  60
42  59
43  58
44  57
45  56
46  55
47  54
48  53
49  52

Хотя может быть я неправильно Паскаль в С++ перевёл. Я уже чёт забыл с ихними циклами

for i := n - 1 downto (n + 1) div 2 do
for i := 2 to trunc(sqrt(n)) do

условие окончания цикла строгое или нет? Я сделал строгое.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #34 : 26-11-2009 13:59 » 

N=100
максимальная сумма <= 100+100-2

ты начинаешь перебор гирь от 99. Почему?

Где я начинаю перебор гирь от 99?

Смотри, у меня всего 100 гирь: 1, 2, 3, ... 100

1. Я нахожу наибольшее простое число на этом интервале - это 97.
2. 97 соостоит РОВНО из (97-1)/2=48 пар ВСЕХ чисел до него.
3. Остаётся остаток из четырёх гирь.

Кстати паскалевская пржка делает тчно также, но только в том случае если N изначально простое.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #35 : 26-11-2009 14:01 » 

Джон, блин!!!
99+97 - это максимальная сумма двух гирь!!!
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #36 : 26-11-2009 14:02 » 

96   +   1   =   97
95   +   2   =   97
94   +   3   =   97
93   +   4   =   97
92   +   5   =   97
91   +   6   =   97
90   +   7   =   97
89   +   8   =   97
88   +   9   =   97
87   +   10   =   97
86   +   11   =   97
85   +   12   =   97
84   +   13   =   97
83   +   14   =   97
82   +   15   =   97
81   +   16   =   97
80   +   17   =   97
79   +   18   =   97
78   +   19   =   97
77   +   20   =   97
76   +   21   =   97
75   +   22   =   97
74   +   23   =   97
73   +   24   =   97
72   +   25   =   97
71   +   26   =   97
70   +   27   =   97
69   +   28   =   97
68   +   29   =   97
67   +   30   =   97
66   +   31   =   97
65   +   32   =   97
64   +   33   =   97
63   +   34   =   97
62   +   35   =   97
61   +   36   =   97
60   +   37   =   97
59   +   38   =   97
58   +   39   =   97
57   +   40   =   97
56   +   41   =   97
55   +   42   =   97
54   +   43   =   97
53   +   44   =   97
52   +   45   =   97
51   +   46   =   97
50   +   47   =   97
49   +   48   =   97
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #37 : 26-11-2009 14:03 » 

а что такое "строгое" окончание  цикла?
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #38 : 26-11-2009 14:04 » 

Джон, да отвяжись ты от простых чисел!!!
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #39 : 26-11-2009 14:08 » 

Джон, блин!!!
99+97 - это максимальная сумма двух гирь!!!

Хе? Ты сейчас о чём? При чём здесь максимальная сумма двух гирь (хотя смысла этого выражения я не пнимаю - разве у двух гирь может быть несколько сумм? максимальная и немаксимальная? Ага )? Ну может быть. Ну и что? Это не важно. Я перебрал все гири и у меня осталось только четыре.

97
98
99
100

Из них я могу получить ещё две пары в сумме дающие простые числа. Таким образом я получаю (конечно аналитически) теоретически максимально возможное число пар - 50.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #40 : 26-11-2009 14:09 » 

а что такое "строгое" окончание  цикла?

i<n  vs  i<=n
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #41 : 26-11-2009 14:10 » 

Джон, да отвяжись ты от простых чисел!!!

Почему? Это же условие, сумма двух гирь должна быть простым числом.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #42 : 26-11-2009 14:12 » 

я говорю о том, что 99+98 может быть простым число и входить во множество по 2 из ста.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #43 : 26-11-2009 14:21 » 

"Меня терзают смутные сомнения" (с)

Похоже мы с тобой о разных вещах говорим. Что значит "множество по 2 из 100"? Что эта пара должна учитываться? Конечно, я же написал:

Для очистки совести:

97 +  98 = 195
99 + 100 = PRIME 199 +1

97 + 100 = PRIME 197
98 + 99   = PRIME 197

Первая комбинация даёт только одну пару, вторая - две.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #44 : 26-11-2009 14:42 » 

Ну короче всё прояснилось. Это я накосячил - неправильно циклы перевёл, проверка условия нестрогая. Получается ровно 50. Там как раз пары 50 и 51 не хватает. Собственно это и навело на ошибку.

А жаль. Жаль
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #45 : 26-11-2009 14:43 » 

Код выложить?
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #46 : 26-11-2009 14:44 » 

та показуй Улыбаюсь
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #47 : 26-11-2009 14:49 » 

Вариант когда N=2 я не стал обрабатывать, это и так понятно:

Код:
BOOL CPrimeNumberDlg::Easy(long n)
{
for(long i=2; i<=(int)(sqrt((double)n)); i++)
{
if((n%i)==0)
{
return FALSE;
}
}
return TRUE;
}

long CPrimeNumberDlg::FindEasy(long n)
{
for(long i=n+1; i<=999999; i++)
{
if(Easy(i))
{
return i;
}
}
return 0;
}

void CPrimeNumberDlg::OnBnClickedButton2()
{
UpdateData(TRUE);

int nPairCnt = 0;

int n = m_nMax;

if(Easy(n))
{
for(long i=n-1; i>=(n+1)/2; i--)
{
TRACE("%d\t%d\n", i, n-i);
nPairCnt++;
}
}
else
{
long m = 0;
while(n>0)
{
m = FindEasy(n);
if( (m==0) || (m>=2*n) )
{
break;
}

for(long i = m- n; i<=m/2; i++)
{
TRACE("%d\t%d\n", i, m-i);
nPairCnt++;
}
n = m - n - 1;
}
}

TRACE1("Pairs: %d\n", nPairCnt);
}
« Последнее редактирование: 26-11-2009 14:55 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #48 : 26-11-2009 14:56 » 

Код подправил. Во вспомогательных ф-ях циклы for, а то получалось что 15 тоже простое число.

Вот проект (MFC VS .NET 2003), если кто захочет поиграться.

* PrimeNumber.zip (61.17 Кб - загружено 642 раз.)
« Последнее редактирование: 26-11-2009 15:01 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Страниц: 1 [2]  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines