[c++] Простые гири

[Solnce]

Всем здравствуйте!
Помогите пожалуйста со следующей задачей:
Имеются гири с массами: 1 г, 2 г, ..., N г (N≤500000). Написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.
Входные данные
Входной файл INPUT.TXT содержит число N.
 
Выходные данные
В выходной файл OUTPUT.TXT выводится список найденных пар. Все числа в выходном файле разделяются пробелами и (или) символами перевода строки.
алгоритм в принципе  я  придумала, у меня проблемы с реализацией, потому что сделать надо при помощи связанного списка.
НАДЕЮСЬ кто-нибудь ОТКЛИКНЕТСЯ и поможет мне с моей проблемой.

[Алексей++]

Показывай код, поможем, почему не помочь ?

[Solnce]

Код:

#pragma once

#ifndef WEIGHT_H
#define WEIGHT_H
#include <iostream>

using namespace std;
const int N = 500000;

class _08_weight {
public:	
	_08_weight(void);
	~_08_weight(void);

protected:
	FILE *input;
	FILE *output;
struct Node
	{
		int item;
		Node *next;
	};
		Node *point;
		Node *find(int index) const;
	
public:
	
	int size;
	bool isEmpty() const;
	int getLength() const;
	void remove (int index)
		throw (ListIndexOutOfRangeException);
	void retrieve(int index,int& dataItem) const
		throw (ListIndexOutOfRangeException);
	

	int simple_number(int sum){};
	int pair(Node *point);
	class complete:public ERROR{};


};

#endif 

это пока  я только написала хэдер а вот некоторая реализация, не посмотрите ошибки тоже

[Solnce]

Код:

#include "solution_36.h"
#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <math.h>
using namespace std;

bool _08_weight::isEmpty() const
{
	return bool (size == 0);
}
int _08_weight::getLength() const
{
	return size;
}
_08_weight::Node *_08_weight::find(int index) const
{
	if ((index <1) || (index > getLength()))
		return NULL;
	else
	{
		Node *cur = point;
		for (int skip =1; skip < index; ++skip)
			cur = cur -> next;
		return cur;
	}
}
void _08_weight::retrieve(int index, int& dataItem) const
{
	if ((index <1) || (index > getLength()))
		throw ListIndexOutOfRangeException(
		"ListIndexOutOfRangeException: неверный индекс");
	else
	{
		Node *cur = find(index);
		dataItem  = cur ->item;
	}
}
void _08_weight::remove(int index)
{
	Node *cur;
	if ((index <1) || (index > getLength()))
		throw ListIndexOutOfRangeException(
		"ListIndexOutOfRangeException: неверный индекс");
	else
	{
		--size;
		if (index==1)
		{
			cur = point;
			point = point ->next;
		}
		else
		{
			Node *prev = find(index - 1);
			cur = prev -> next; //сохраняем указатель на узел
			prev -> next = cur -> next;
		}
		cur -> next = NULL;
		delete cur;
		cur = NULL;
	}
}

_08_weight::_08_weight()
{
	point = new Node;
}

_08_weight::~_08_weight()
{
	while (!isEmpty())
	remove (1);
}

int _08_weight::simple_number(int is_s)
{
	int k,i=2;
	k = sqrt (is_s);
	while (i != k)
	{
		if (is_s % i = 0) {return 0;}
		i++;
	}
	return 1;
}

int _08_weight::pair(Node *point)
	Node *cur = point;
	Node *prev;
	prev = NULL;
	
	while (cur != NULL)
	{
		prev = cur;
		cur = cur ->next;
		
	}

вообще осталось написать самое трудное т.е., соединение на пары, мой алгоритм звучит так:когда на вход подается число N я проверяю является ли число четным или нет.
если оно четное тогда проверяю так, начиная с единицы если сумма простое число тогда пары (1,N), наращиваю 1 и уменьшаю N т.е. получаю N/2 пар, если не простое тогда иду дальше т.е. если i=1, потом i++ до тех пор пока сумма не даст простое число,оставшуюся часть реализую также, если не четное тогда начинаю с 4 проделываю тоже самое

[Sla]

Solnce, еще раз напиши алгоритм проверки и прочитай вслух

когда на вход подается число N я проверяю
является ли число четным или нет.
если оно четное тогда проверяю так,
   начиная с единицы если сумма простое число тогда пары (1,N), наращиваю 1 и уменьшаю N т.е. получаю N/2 пар,
                                   если не простое тогда иду дальше т.е. если i=1, потом i++ до тех пор пока сумма не даст простое число,оставшуюся часть реализую также,
если не четное тогда начинаю с 4 проделываю тоже самое

Что такое четное/нечетное, простое/непростое?

зы простое/непростое, четное/нечетное - знаю что это такое, потому и спрашиваю.

[Solnce]

число называется простым если делится только на себя и на 1, иначе оно не простое.
число называется четным если оно делится на 2, иначе нечетным

[RXL]

Solnce, лучше составь таблицу простых чисел от 1 до максимального требуемого тебе (руками или вычислив) - там удобнее и быстрее будет проверять.

[Sla]

функция определения простое/не простое - єто всего лишь часть задачи, но вносящее ограничение.

1+2 = 3 простое
3+4 = 7 простое
5+6 = 11 простое
7+8+9+10.... а вдруг не простое? тогда
  7+9+10 и т.д.

[Solnce]

вот функция которая проверяет простое или нет

Код:

int _08_weight::simple_number(int is_s)
{
	int k,i=2;
	k = sqrt (is_s);
	while (i != k)
	{
		if (is_s % i = 0) {return 0;}
		i++;
	}
	return 1;
}

[Sla]

извините не знающего, а это

int k,i=2;
k = sqrt (is_s);

будет работать?

[RXL]

Конечно не будет. Нужно составлять список уже найденных простых чисел и тестировать на деление без остатка для этих чисел из диапазона [2..CEIL(SQRT(number))]. Новое найденное простое надо добавлять в этот список.

[Джон]

ИМХО за код рановато взялись. С логикой не всё ясно. Знаю только что проверка является ли число простым дело нетривиальное. Согласен с RXL, лучше сделать (сгенерировать) таблицу простых чисел, только сначала надо определить максимальное требуемое простое число. Для определённости можно сказать, что оно будет не больше чем 500 000 + 500 000 (N + N).
Отсюда плясать.

[RXL]

http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE

http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

Offtopic:

Забавно, что (2ⁿ - 1) являются простыми числами

И совсем изврат:

Полиномиальная формула

Множество положительных значений многочлена

Код:

    (k + 2)(1 − [wz + h + j − q]2 − [(gk + 2g + k + 1)(h + j) + h − z]2 − [2n + p + q + z − e]2 −
    [16(k + 1)3(k + 2)(n + 1)2 + 1 − f2]2 − [e3(e + 2)(a + 1)2 + 1 − o2]2 − [(a2 − 1)y2 + 1 − x2]2 −
    [16r2y4(a2 − 1) + 1 − u2]2 − [((a + u2(u2 − a))2 − 1)(n + 4dy)2 + 1 − (x + cu)2]2 − [n + l + v − y]2 −
    [(a2 − 1)l2 + 1 − m2]2 − [ai + k + 1 − l − i]2 − [p + l(a − n − 1) + b(2an + 2a − n2 − 2n − 2) − m]2 −
    [q + y(a − p − 1) + s(2ap + 2a − p2 − 2p − 2) − x]2 − [z + pl(a − p) + t(2ap − p2 − 1) − pm]2)

в точности совпадает с множеством простых чисел, если встречающиеся в нем переменные пробегают все неотрицательные целые значения.[2][3][4] Данный результат является частным случаем доказанной Юрием Матиясевичем диофантовости любого эффективно перечислимого множества.

[Sla]

Джон, я потому и сказал, что принадлежность к простому - есть частная задача.
и показал "логику" на первых четырех выборках.

[Джон]

Ну собственно говоря задачка как оказалось олимпиадная. В инете полно про неё. Я думаю автор пытается реализовать вот эту логику:
http://g6prog.narod.ru/g6_1074.html


Вот здесь даже прожка на Паскале есть:
http://www.school10.org.ua/info/olimp/ol3_07.htm

[Sla]

Учила мама - читай ТЗ

речь идет о парах чисел

[Sla]

тогда все проще

1+2 = 3 простое
3+4 = 7 простое
5+6 = 11 простое
7+8 - не простое
  7+9 - непростое
    7+10 простое
а алгоритм перебора уже виден на бумаге

[Джон]

Слав, а 1+4 = 5 тоже простое.

[Sla]

я рассматриваю вариант, что каждой гири по одной

Т.е. составить все пары
А вот максисмально возможное количество пар это будет множество, например при n=7

1 2
3 4
5 7
мощность = 3

или
1 4
2 5   upd(было 3 5)
мощность = 2
или ...

Где максимально?

[Вад]

Согласен с Джоном, задача проще решается с обратной стороны: сначала найти все простые числа, которые можно выразить суммой двух чисел <=500000 (то есть, простые числа в диапазоне 2..999999). А потом каждое простое раскладывать на все возможные суммы слагаемых. Вот и всё.
Решето Эратосфена и разложение оставшихся чисел на суммы двух слагаемых.

я рассматриваю вариант, что каждой гири по одной

Использовать две гири одного веса бессмысленно по условию задачи - в сумме требуется получить простое число И, как я понимаю, нужно получить лишь уникальные пары.

[Джон]

Маленькая поправочка - 3 5 наверное 2 5? Думаю что ДА.

Продолжим:

А так?

6 + 1 = 7

2 + 5 = 7

4 + 3 = 7

Заметь, "лишняя" гиря с весом 7 может пригодиться для получения пары на каком-нить шаге j. А может быть и нет... Впрочем, как и "лишняя" гиря с весом 6 из твоего варианта. К чему это я? К тому, что можно ли строго доказать, что "мощность" есть величина постоянная для конкретной логики и не зависит от числа гирь? Ведь я могу использовать 2 и 6 для получения пар с другими гирями.
Например, подняв планку до 8 получаем:

1 2
3 4
5 7

сравни с моим вариантом:

1 4
2 5
6 7
8 3

Ооопаньки. 

[Sla]

Ок.
Давайте переформулирую вопрос.
Написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался числом кратным 7.

Что-то от этого изменилось? Ушла проверка на условие? Или от этого основная задача усложнилась?

[Джон]

Вад, при всём при том, что их в этом диапазоне всего лишь 78498

[Джон]

Слав, а почему 7ми?

[Sla]

Джон, мне так захотелось

[Sla]

я в таких "теоремах" не силен. (3+5 - ошибка, полезу исправлять)

зы. Топик перетекает в аналог про множество строк. Ждем автора.

[Джон]

Короче. Такая идея, для нахождения максимального числа пар (не уверен, что оно будет максимальным, хочу критику услышать )

Собственно почему проблема (может только у меня в голове)? Я почти уверен, что число пар есть ф-я от алгоритма нахождения пар, который в свою очередь является функцией от числа гирь. Посему:

Максимальное количество пар (просто пар) для числа N - очевидно ~N/2 (~ для нечётных N), в идеале к нему надо стремиться.

Значит, находим наибольшее простое число PrimeMax < N (для 500 000 это 499979) - это просто. Теперь всё совсем просто:

499979 = 499978 + 1
499979 = 499977 + 2
499979 = 499976 + 3
499979 = 499975 + 4
499979 = 499974 + 5
499979 = 499973 + 6
...

Короче говоря я получаю сразу и гарантировано (499979-1)/2 пар. (исправлено - конечно только половина )

Теперь остаётся только остаток = N - PrimeMax

Дёт выигрыш по времени - ведь мне не нужно проверять каждую сумму на "простоту", а только оставшиеся числа.

Остаётся неуверенность в максимальности такой "комбинации".

Сумбурно, потому что в голове тоже сумбурно. Попробую ещё подумать.

[Джон]

1 + 2 =        PRIME 3
3 + 4 =        PRIME 7
5 + 6 =        PRIME 11
7 + 8 = 15
7 + 9 = 16
7 + 10 =        PRIME 17
11 + 12 =        PRIME 23
13 + 14 = 27
13 + 15 = 28
13 + 16 =        PRIME 29
17 + 18 = 35
17 + 19 = 36
17 + 20 =        PRIME 37
21 + 22 =        PRIME 43
23 + 24 =        PRIME 47
25 + 26 = 51
25 + 27 = 52
25 + 28 =        PRIME 53
29 + 30 =        PRIME 59


Выпали:

8+9=17
14+15=29
18+19=37
26+27=53

[Sla]

почему взято число 500000? Просто от фонаря.
Если учитывая  некие условия про ПАРЫ, то максимальное простое число >= N+N-2
Количество пар = число сочетаний по два из множества 1..
А вот о максимальном количестве пар, думаю, что только перебор.
1. начиная от 1 вычислить мощность множества сочетаний.
2. и т.д. каждый раз помечая элементы, входящие в это множество. 

[Джон]

500000 - это предел установленный в ТЗ. Но это не важно. Я просто хочу эмпирически показать, что "мой" метод даст больше пар, чем последовательный перебор. Вот что получается, например, на отрезке до 100.

Имеем

PrimeMax = 97

96/2 = 48

96 + 1
95 + 2
94 + 3
...
49 + 48

Остаются только:

97
98
99
100

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

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

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

Таким образом я  "потерял" только две пары.

А что даёт последовательный перебор?

1 + 2 =        PRIME 3
3 + 4 =        PRIME 7
5 + 6 =        PRIME 11
7 + 8 = 15
7 + 9 = 16
7 + 10 =        PRIME 17
11 + 12 =        PRIME 23
13 + 14 = 27
13 + 15 = 28
13 + 16 =        PRIME 29
17 + 18 = 35
17 + 19 = 36
17 + 20 =        PRIME 37
21 + 22 =        PRIME 43
23 + 24 =        PRIME 47
25 + 26 = 51
25 + 27 = 52
25 + 28 =        PRIME 53
29 + 30 =        PRIME 59
31 + 32 = 63
31 + 33 = 64
31 + 34 = 65
31 + 35 = 66
31 + 36 =        PRIME 67
37 + 38 = 75
37 + 39 = 76
37 + 40 = 77
37 + 41 = 78
37 + 42 =        PRIME 79
43 + 44 = 87
43 + 45 = 88
43 + 46 =        PRIME 89
47 + 48 = 95
47 + 49 = 96
47 + 50 =        PRIME 97
51 + 52 =        PRIME 103
53 + 54 =        PRIME 107
55 + 56 = 111
55 + 57 = 112
55 + 58 =        PRIME 113
59 + 60 = 119
59 + 61 = 120
59 + 62 = 121
59 + 63 = 122
59 + 64 = 123
59 + 65 = 124
59 + 66 = 125
59 + 67 = 126
59 + 68 =        PRIME 127
69 + 70 =        PRIME 139
71 + 72 = 143
71 + 73 = 144
71 + 74 = 145
71 + 75 = 146
71 + 76 = 147
71 + 77 = 148
71 + 78 =        PRIME 149
79 + 80 = 159
79 + 81 = 160
79 + 82 = 161
79 + 83 = 162
79 + 84 =        PRIME 163
85 + 86 = 171
85 + 87 = 172
85 + 88 =        PRIME 173
89 + 90 =        PRIME 179
91 + 92 = 183
91 + 93 = 184
91 + 94 = 185
91 + 95 = 186
91 + 96 = 187
91 + 97 = 188
91 + 98 = 189
91 + 99 = 190
91 + 100 =        PRIME 191


Только 25.