Выборка чисел - Помощь студентам - Страница 2

ds.Dante · 13.11.2009, 10:18

Если элементов меньше 25, то без проблем.

uber · 13.11.2009, 10:36

получается - на ограниченном множестве.. хотя бы до 30.. это вполне реализуемо

LeBron · 13.11.2009, 11:52

Цитата:

Сообщение от Serge_Bliznykov

грубо говоря. пусть программа перебирает 10 чисел за 1 минуту. Но тогда (очень приблизительно, но порядок верен) 11 чисел будет обработано за 11 минут. 12 чисел за 132 минуты и т.д. мысль понятна?

Не пугайте так человека

С учетом количества вариантов перебора, каждое следующее число дает только удвоение. Еще чуть больше с учетом увеличения розрядности, но все же... Если 10 чисел в минуту, то 11 - теоретически в 2 минуты 12 секунд.

Цитата:

Сообщение от ds.Dante

Если элементов меньше 25, то без проблем.

Какие примерно ограничения времени?
Если 25 элементов, то выполнение укладываеться в 2 секунды. Для 30 елементов думаю не трудно уложиться в минуту. При более-менее "не-деревянно-бронированом" компе - еще быстрее.

Serge_Bliznykov · 14.11.2009, 13:34

Цитата:

Сообщение от LeBron

Не пугайте так человека С учетом количества вариантов перебора, каждое следующее число дает только удвоение. Еще чуть больше с учетом увеличения розрядности, но все же... Если 10 чисел в минуту, то 11 - теоретически в 2 минуты 12 секунд.

сначала хотел оспорить Ваше утверждение.
Полез в теорию. (вот тут - Сочетание — Википедия, а вот здесь online калькулятор - Нахождение числа сочетаний из n по k)
так вот, согласно теории Вы правы. но всё равно, при увеличении числа на единичку, идёт УДВОЕНИЕ числа вариантов. Так что всё упирается в эффективность реализации перебора, в количество чисел в выборке, вероятности нахождения нужной суммы, ну и в мощность используемого компьютера, разумеется.

Поэтому, если для 25 элементов расчёт укладывается в две секунды (кстати, если не жалко - дайте плиз исходничек, будет очень любопытно поизучать/потестировать!), то для 26 - 4 сек, для 27 - 8 сек, для 28 - 16 сек. для 29 - 32 сек. для 30 - 1 мин 04 сек., для 31 - 2 м 8 сек, для 32 - 4 м 16 сек, для 33 - 8 м 32 сек, для 34 - 17 м 04 сек... вы ещё не утомились?

продолжив ряд нетрудно убедиться, что уже для 45 чисел потребуется "всего" 582 часа..
а для 50 чисел - 18641 час (это чуть больше двух лет)...

LeBron · 14.11.2009, 14:39

Цитата:

Сообщение от Serge_Bliznykov

Поэтому, если для 25 элементов расчёт укладывается в две секунды (кстати, если не жалко - дайте плиз исходничек, будет очень любопытно поизучать/потестировать!), то для 26 - 4 сек, для 27 - 8 сек, для 28 - 16 сек. для 29 - 32 сек. для 30 - 1 мин 04 сек., для 31 - 2 м 8 сек, для 32 - 4 м 16 сек, для 33 - 8 м 32 сек, для 34 - 17 м 04 сек... вы ещё не утомились?

продолжив ряд нетрудно убедиться, что уже для 45 чисел потребуется "всего" 582 часа..
а для 50 чисел - 18641 час (это чуть больше двух лет)...

Это понятно, для большого количества чисел не проходит полный перебор. По поводу "пугания" - я имел ввиду то, что 10-12 - еще далеко не критическое число для перебора. По поводу самого исходника - сейчас банально нету времени/желания его писать, если хотите посмотреть - чуть попозже напишу. Сейчас могу предложить посмотреть на вот эту задачу... е.. даже не знаю, в этом разделе ссылки запрещены, так что условие копирну, за ссылками в личку... Примерные подсчеты показывают, что если перебор 14 миллионов чисел (в этой задаче) укладываеться в 0.25 секунды, то перебор 32 миллионов в 2 секунды уложиться без особых проблем. Даже с учетом того, что числа будут в 5/3 раза более длинными и будет больше переходов розрядов.
Задача: "В волшебной стране используются монетки достоинством A1, A2,..., AM. волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные

Во входном файле INPUT.TXT записано сначала число N (1 <= N <= 10^9), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 10^9).

Выходные данные

В выходной файл OUTPUT.TXT выведите количество монет, которое придется отдать волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Если решений несколько, выведите вариант, в котором волшебный человек отдаст наименьшее возможное количество монет. Если без сдачи не обойтись, то выведите одно число 0. Если же у волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).

Сдесь перебор всех 3^15 вариантов в моем решении показал время 0.267 секунды. Сейчас я вижу, что мое решение даже немного неоптимально, и можно написать еще быстрее. Лучшие решения методом перебора на этой задаче показывают время меньше 0.15 секунды. (при желании получить подтверждающие ссылки - обращаемся в личку, отвечу). Вот мой АС код этой задачи (из изменений - только попытка форматирования для улучшения восприятия посторонними и удаление ненужных закоментированых кусков кода - тоже для улучшения восприятия)

Код:

var input,output:text; n,i,j,g,nm,ans,t:integer;ara:array[0..1000] of integer;ar,arq:array[0..1000] of integer; ts,sum,a:integer;
begin
assign(input,'input.txt');reset(input);
 assign(output,'output.txt');rewrite(output);
readln(input,a,n);
ans:=10000;

for i:=1 to n do begin
read(input,ar[i]);ts:=ts+2*ar[i];end;

  if ts<a then writeln(output,'-1') else

  begin

     ara[1]:=3;for i:=2 to 15 do begin ara[i]:=3*ara[i-1];end;

 for i:=1 to ara[n] do begin if arq[n]<2 then begin
  inc(arq[n]);sum:=sum+ar[n];inc(nm);
  end
 else
  begin
   g:=n;while arq[g]>1 do begin sum:=sum-ar[g]*arq[g];dec(nm,arq[g]);arq[g]:=0;dec(g);end;

 inc(arq[g]);sum:=sum+ar[g];inc(nm);end;
if sum=a then begin if nm<ans then ans:=nm;end;end;

 if ans>1000 then writeln(output,'0') else writeln(output,ans);   end;

close(output);close(input);
end.

uber · 17.11.2009, 14:48

это все верно что вы говорите...но хотелось получить вашу оценку..моему предложению..
я придумал перебирать суммы из сортрованных столбцов, примерно так:
для 0<x<=1 и 5<x<=5.9

Код:

procedure TForm1.Button1Click(Sender: TObject);
var uslovie,interval,variant:real;
        i,j:integer;

begin
interval:=5.9;
for i:=1 to Form1.StringGrid1.rowcount do
	begin
    for j:=1 to Form1.StringGrid1.rowcount do
    begin
    uslovie:=interval-strtofloat(Form1.StringGrid1.cells[6,i]);
    variant:=strtofloat(Form1.StringGrid1.cells[6,i])+ strtofloat(Form1.StringGrid1.cells[1,j]);
    if (variant <= interval) and (variant >= uslovie) then
    Memo1.Lines.Add('vairant=' + Form1.StringGrid1.cells[1,j] + '+' + Form1.StringGrid1.cells[6,i]);
    end;
    end;
  end;
end.

ошибочка...получилось, что выводит результат только для [6,1] , а надо чтобы шагал до [6,RowCount]

ds.Dante · 17.11.2009, 16:03

Цитата:

Сообщение от Serge_Bliznykov

кстати, если не жалко - дайте плиз исходничек, будет очень любопытно поизучать/потестировать!

Цитата:

Сообщение от LeBron

По поводу самого исходника - сейчас банально нету времени/желания его писать, если хотите посмотреть - чуть попозже напишу.

Думаю, это относилось ко мне. :) Возмьу сегодня из дома, если не забуду. Только там одна ошибка была - где-то учитывались только младшие 8 разрядов регистра. Я не стал исправлять, когда понял, что оптимизация незначительна.

uber · 17.11.2009, 22:38

Короче....
я делаю таблицу, с заголовками:

Код:

Form1.StringGrid1.cells[1,0]:=' 0 < x =< 1 ';
        Form1.StringGrid1.cells[2,0]:=' 1 < x =< 2';
        Form1.StringGrid1.cells[3,0]:=' 2 < x =< 3';
        Form1.StringGrid1.cells[4,0]:=' 3 < x =< 4';
        Form1.StringGrid1.cells[5,0]:=' 4 < x =< 5';
        Form1.StringGrid1.cells[6,0]:=' 5 < x =< 5.9';

затем перебираю варианты между столбцами: (на скору руку):

Код:

procedure TForm1.Button1Click(Sender: TObject);
var     interval,variant:real;
        i,j,ii,jj,iii,jjj:integer;

begin
interval:=5.9;
for i:=1 to (Form1.StringGrid1.rowcount-1) do
        for j:=1 to (Form1.StringGrid1.rowcount-1) do
        begin
        variant:=strtofloat(Form1.StringGrid1.cells[6,i])+strtofloat(Form1.StringGrid1.cells[1,j]);
        if (variant<=interval) then Memo1.Lines.Add('variant= '+ Form1.StringGrid1.cells[1,j] + '+' + Form1.StringGrid1.cells[6,i]);

for ii:=1 to (Form1.StringGrid1.rowcount-1) do
        for jj:=1 to (Form1.StringGrid1.rowcount-1) do
        begin
        variant:=strtofloat(Form1.StringGrid1.cells[5,ii])+strtofloat(Form1.StringGrid1.cells[2,jj]);
        if (variant<=interval) then Memo1.Lines.Add('variant= '+ Form1.StringGrid1.cells[2,jj] + '+' + Form1.StringGrid1.cells[5,ii]);
        end;

for iii:=1 to (Form1.StringGrid1.rowcount-1) do
        for jjj:=1 to (Form1.StringGrid1.rowcount-1) do
        begin
        variant:=strtofloat(Form1.StringGrid1.cells[4,iii])+strtofloat(Form1.StringGrid1.cells[3,jjj]);
        if (variant<=interval) then Memo1.Lines.Add('variant= '+ Form1.StringGrid1.cells[3,jjj] + '+' + Form1.StringGrid1.cells[4,iii]);
        end;
end;
end;

end.

он выдает все варианты для условиня (не больше 5,9)

а дальше...как убрать повторы..? чтобы каждый элемент(тоесть ячейка) был однажды искользован?

From Stilet: Не знаю где ты код выделять так научился, но у нас для него есть специальная кнопка # - попрошу ей пользоваться для оформления в посте кода.

ds.Dante · 18.11.2009, 10:17

[табуляция 4 символа]

Код:

#include <windows.h>
#include <fstream>
#define qwe 10
using namespace std;

void Error	(int n);

int __stdcall WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)
{
	int			*Arr, Approx;
	int			N, NCombs;
	ifstream	fin ("input.txt", ios::in);

	if (lpCmdLine[0])
	{
		MessageBoxA (NULL, "Approx 1.0\n© 2007 Fedorkov Dmitry.\nThe program find the nearest sum.\n\ninput.txt format:\nfirst string – approximation;\nother strings – sum set.\n\noutput.txt:\nfirst string – the nearest found sum;\nother strings – numbers of elements.", "About Approx", MB_ICONINFORMATION);
		return 0;
	}
	if (!fin)
		Error (1);
	fin.seekg (0, ios::end);								// Get file size...
	N = fin.tellg();
	fin.seekg (0, ios::beg);
	N /= 2;													// ...now the max number of numbers (theoretically)
	if (N<2)
		Error (2);
	Arr = new(nothrow) int [N];
	if (!Arr)
		Error (3);

	fin >> Approx;
	if (!fin.good())										// if read error
		Error (2);
	for (N=0; fin.good(); N++)
		fin >> Arr[N];
	fin.close();
	NCombs = 1 << N;
	if (N<3 || N>=32)										// if no numbers or too much
		Error (2);
	if (N>28)
		if (MessageBoxA (NULL, "This operation can take much time.\nDo you want to continue?", "Warning", MB_YESNO+MB_ICONWARNING) != IDYES) 
			return 0;
	ofstream fout;
	fout.open ("output.txt", ios::out);						// Output file
	if (!fout.is_open())
		Error (4);

	int	NumElems = 0;
	int	CurrNumElems = 0;
	int	Diff = abs(Approx);
	int	SetBits;

	__asm
	{
					// 1) Init counters & accumulators
		mov		esi, Diff		// Diff = abs(Approx)
		xor		edi, edi		// CurrSum = 0
		xor		eax, eax		// G = 0 (Gray code)
		mov		ecx, NCombs		// for (int i=NCombs-2...
		dec		ecx

MainLoopStart:

					// 2) Find next Gray code
		mov		eax, qwe
		xor		edx, edx		// reset inner counter
		xor		ebx, ebx
		add		al, bl		// test eax on parity (error?!)
		jp		NoIncr1
		inc		bh
NoIncr1:
		add		ah, bl
//		jp		NoIncr2
		jp		SkipShiftLoop	// is even?

		mov		ebx, eax		// save G
ShiftLoop:
		inc		edx				// counter++
		shr		ebx, 1			// G >>= 1
		jnc		ShiftLoop		// Is odd?
SkipShiftLoop:					// Now in edx is the number of bit that is to change

		mov		ebx, 1			// make xor mask
		xchg	ecx, edx		// temporary use edx in cl for...
		shl		ebx, cl			// ...ebx >>= cl...
		xchg	ecx, edx		// and revert back
		xor		eax, ebx		// invert THIS bit

					// 3) Add / subtract
		test	eax, ebx		// add or subtract?
		jz		Subtract
		mov		ebx, Arr		// CurrSum += Arr[i]
		add		edi, [ebx+4*edx]
		inc		CurrNumElems	// CurrNumElems++
		jmp		NoSubtract
Subtract:
		mov		ebx, Arr		// CurrSum -= Arr[i]
		sub		edi, [ebx+4*edx]
		dec		CurrNumElems	// CurrNumElems--
NoSubtract:

					// 4) if (CurrDiff<Diff || (CurrDiff==Diff && CurrCount<=Count)) than save state
		mov		ebx, Approx		// CurrDiff = Approx-Sum
		sub		ebx, edi
		jns		NoInvert		// CurrDiff = abs (CurrDiff)
		neg		ebx
NoInvert:
		cmp		ebx, esi
		jg		DontSave		// if CurrDiff > Diff than skip
		jl		Save			// if CurrDiff < Diff than save
		mov		edx, CurrNumElems // CurrDiff==Diff; if CurrNumElems>=NumElems than skip
		cmp		edx, NumElems
		jge		DontSave
Save:
		mov		SetBits, eax	// SetBits = eax
		mov		esi, ebx		// Diff = CurrDiff
		mov		edx, CurrNumElems // NumElems = CurrNumElems
		mov		NumElems, edx
DontSave:
		loop	MainLoopStart
	}

	int Sum = 0, SetBits2 = SetBits;
	for (int i=0; i<N; i++)
	{
		if (SetBits & 1)
			Sum += Arr[i];
		SetBits >>= 1;
	}
	fout << Sum << endl;
	for (int i=0; i<N; i++)
	{
		if (SetBits2 & 1)
			fout << i+1 << endl;
		SetBits2 >>= 1;
	}
	fout.close();
	return 0;
}

void Error (int n)
{
	switch (n)
	{
		case 1:  MessageBoxA (NULL, "Cannot open file \"input.txt\".",			"Error", MB_ICONERROR); break;
		case 2:  MessageBoxA (NULL, "File \"input.txt\" has illegal format.",	"Error", MB_ICONERROR); break;
		case 3:  MessageBoxA (NULL, "Cannot allocate memory.",					"Error", MB_ICONERROR); break;
		case 4:  MessageBoxA (NULL, "Cannot open file \"output.txt\".",			"Error", MB_ICONERROR); break;
		default: MessageBoxA (NULL, "Unknown error.",							"Error", MB_ICONERROR);
	}
	exit (n);
}

ds.Dante · 18.11.2009, 10:20

В 68-й строке проверяется только 8 младших бит, в некоторых случаях программа может работать неправлильно.

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

Алгоритм блока __asm на псевдокоде (G - код Грея)

Код:

	int Diff = abs(Approx);
	int	CurrSum = 0;
	int	G = 0;
	for (int ecx=NCombs-1; ecx>0; ecx--)
	{
#pragma region Find next Gray code
		if (sum of G is even)
			edx = 0;
		else
		{
			edx = (find number of lowest "1" bit of eax);
			edx++;
		}
		ebx = 1 << edx;					// Make xor mask
		G ^= ebx;
		invert G[edx];					// EDX-th bit of EAX
#pragma endregion

		if (G[edx])						// Add or subtract?
		{
			CurrSum += Arr[edx];
			CurrNumElems++;
		}
		else
		{
			CurrSum -= Arr[edx];
			CurrNumElems--;
		}
		CurrDiff = abs (CurrSum-Approx);
		if ((CurrDiff<Diff) | ((CurrDiff==Diff) & (CurrNumElems<NumElems)))
		{
			Diff = CurrDiff;
			NumElems = CurrNumElems;
		}
	}

17.11.2009, 14:48	#16
uber Регистрация: 12.11.2009 Сообщений: 9	это все верно что вы говорите...но хотелось получить вашу оценку..моему предложению.. я придумал перебирать суммы из сортрованных столбцов, примерно так: для 0<x<=1 и 5<x<=5.9 Код: procedure TForm1.Button1Click(Sender: TObject); var uslovie,interval,variant:real; i,j:integer; begin interval:=5.9; for i:=1 to Form1.StringGrid1.rowcount do begin for j:=1 to Form1.StringGrid1.rowcount do begin uslovie:=interval-strtofloat(Form1.StringGrid1.cells[6,i]); variant:=strtofloat(Form1.StringGrid1.cells[6,i])+ strtofloat(Form1.StringGrid1.cells[1,j]); if (variant <= interval) and (variant >= uslovie) then Memo1.Lines.Add('vairant=' + Form1.StringGrid1.cells[1,j] + '+' + Form1.StringGrid1.cells[6,i]); end; end; end; end. ошибочка...получилось, что выводит результат только для [6,1] , а надо чтобы шагал до [6,RowCount] Последний раз редактировалось Stilet; 18.11.2009 в 09:09.

18.11.2009, 10:20	#20
ds.Dante Старожил Регистрация: 06.08.2009 Сообщений: 2,992	В 68-й строке проверяется только 8 младших бит, в некоторых случаях программа может работать неправлильно. У меня тогда был спарвочник только по инструкциям 286-го процессора. Для оптимизации я проверял по тому же справочнику количество тактов на опкод, тогда я не знал, что для новых процов эти величины могут быть другими. Алгоритм блока __asm на псевдокоде (G - код Грея) Код: int Diff = abs(Approx); int CurrSum = 0; int G = 0; for (int ecx=NCombs-1; ecx>0; ecx--) { #pragma region Find next Gray code if (sum of G is even) edx = 0; else { edx = (find number of lowest "1" bit of eax); edx++; } ebx = 1 << edx; // Make xor mask G ^= ebx; invert G[edx]; // EDX-th bit of EAX #pragma endregion if (G[edx]) // Add or subtract? { CurrSum += Arr[edx]; CurrNumElems++; } else { CurrSum -= Arr[edx]; CurrNumElems--; } CurrDiff = abs (CurrSum-Approx); if ((CurrDiff<Diff) \| ((CurrDiff==Diff) & (CurrNumElems<NumElems))) { Diff = CurrDiff; NumElems = CurrNumElems; } } Последний раз редактировалось ds.Dante; 18.11.2009 в 10:25.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
работа с выборкой	Inveerto	Общие вопросы Delphi	3	10.04.2011 19:32
Вопрос с выборкой	MHz	Microsoft Office Access	2	13.11.2008 23:19
Помогите с выборкой	VRF	Microsoft Office Excel	5	06.11.2008 01:45
Помогите, пожалуйста, с выборкой	Chel	БД в Delphi	24	05.06.2008 05:00

13.11.2009, 10:18	#11
ds.Dante Старожил Регистрация: 06.08.2009 Сообщений: 2,992	Если элементов меньше 25, то без проблем.

13.11.2009, 10:36	#12
uber Регистрация: 12.11.2009 Сообщений: 9	получается - на ограниченном множестве.. хотя бы до 30.. это вполне реализуемо