مسائل في الخوارزميات

اهلا سهلا يا مازن

اسف قمت بتحرير المشاركة ولكن لا داعي لذكر اسماء

عموما انا موافق وطالما نك صاحب الفكر ابدا بسؤال

أرفع يدي الإثنتين :D

اقتباس

اسف قمت بتحرير المشاركة ولكن لا داعي لذكر اسماء

أعتقد أن ما فعلته هو عين الصواب فيما يخص الأسماء.

و لكن لي اعتراض بسيط على تغييرك عنوان الموضوع، فالفكرة تتلخص في إنشاء موضوع خاص بكل تحدٍ بحيث تكتب فيه الأسئلة و من ثم تتم مناقشة الأجوبة فيه و اختيار العضو صاحب الحل الأفضل (في رأيي ذلك أفضل من 'ضغط' كل التحديات في موضوع واحد)؛ و آثرت ترك مساحة هذا الموضوع للاتفاق على منهجية الأسئلة و الاختيار للحلول الأفضل؛ و كذا لإحصاء العدد المبدئي للأعضاء الراغبين في الانضمام إلى التحديات.

اقتباس

عموما انا موافق

يسرني :)

informat كتب:

أرفع يدي الإثنتين :D

تعجبني الحماسة :lol:

صرنا ثلاثة

اخي مازن لن ننتظر من اراد الانضمام فليفعل

اقتباس

موضوع خاص بكل تحدٍ

برافوا عليك يا مازن هذا ما سنفعله حقا

احب الشباب المتحمس ولكن همسه في الاذن ولكن نصيحة ابتعد عن كلمات مثل تحد لانها تنفر الشباب الخبراء

بالمناسبة من منطقة من اليمن انت ؟

والان جاء دور السؤال لنفرض ان لدينا مجموعة من الاعداد الموجبة داخل مصفوفة هل نستطيع ان تقسمها الى مجموعتين بحيث يكون مجموع الاعداد في الاولى والثانية متساويا

مثال

الحل

انتظر الاجابات

حياكم الله شباب

جواب مبدئي لسؤال رومانوف

ناخذ نصف الاعداد ونجمعهم ونقارن المجموع بالنصف الاخر،،، في حالة عدم التطابق نغير عدد واحد منهم بعدد اخر من السلسلة وهكذا..

وفي النهاية نصل الى عملية من الدرجة:

:rolleyes: يموت الجهاز قبل ما يوصل الى النتيجة المطلوبة

هذه خوارزمية على الماشي مع أمل أن أحسنها بعد ساعات :

أولاً يجب ترتيب الأعداد تصاعدياً من أجل تبسيط التعقيد ...

1- نقوم بحساب مجموع الأعداد جميعها ثم نقسمه على إثنين فيكون لدينا مجموع الأعداد في كل مجموعة

2- نقوم بطرح العدد الأول من ذلك المجموع :

1- إذا كانت النيتجة صفراً فإننا نتوقف عن الحساب و تصبح المجموعة مؤلفة من هذا الرقم ..

2- إذا كانت النتيجة أقل من صفر يتم تجاهل هذ الرقم و إنتقل إلى الرقم الثاني ...

3- إذا كانت النتيجة أكبر تماماً من الصفر عندها نتابع ..

3- نأخذ الرقم الثني و نطرحه من نتيجة الخطوة الأولى :

1- إذا كانت النيتجة صفراً فإننا نتوقف عن الحساب و تصبح المجموعة مؤلفة من هذا الرقم و الرقم الأول ..

2- إذا كانت النتيجة أقل من صفر يتم تجاهل هذ الرقم و نأخذ الرقم الذي بعده ...

3- إذا كانت النتيجة أكبر تماماً من الصفر عندها تصبح المجموعة مؤلفة من هذا الرقم و نتابع ..

و هكذا ...

قد نصل إلى آخر رقم و النتيجة لم تصبح صفراً لذلك نعود خطوة إلى الخلف (خوارزمية تراجعية ) بحيث نتراجع عن أخذ آخر رقم إخترناه و نستبدله بالعدد الذي بعده و هكذا ....

إو بالتالي سنصل حتماً إلى نتيجة 0 و إلا فإن مجموعة الأعداد لا يمكن تقسيمها إلى مجموعتين متساويتين في المجموع ..

سأطبق الخوارزمية على مجموعة الأعداد التي إخترتها أخي romanof :

مجموع الأعداد هي 10 نصفهم 5 ..

الآن :

نأخذ الرقم واحد و نضمه إلى arr1 فيصبح المجموع 4 ..

نأخذ الرقم 2 و نضمه إلى arr1 و يصبح المجموع 2 ..

نأخذ الرقم 3 و نضمعه إلى arr1 و بالتالي يصبح المجموع -1 .. لن نكمل بقية المجموعة و نتراجع خطوة أي نقوم بإزالة الرقم 2 من المجموعة arr1 فيعود المجموع إلى 4

نأخذ الرقم 3 و نطرحه من المجموع فتصبح النتيجة 1 فنضمه إلى arr1 ..

نأخذ الرقم 4 و نطرحه من المجموع فتصبح النتيجة -3 بالتالي نتجاهل هذا الرقم و نتراجع خطوة أي نزيل 3 من المجموعة و يعود المجموع إلى 4 ..

نأخذ الرقم 4 و نطرحه من المجموع فتصبح النتيجة 0 بالتالي نضيف الرقم 4 إلى المجموع ة arr1 و نتوقف ..

فتصبح arr1={1,4} و هو المطلوب ....

romanof كتب:

اخي مازن لن ننتظر من اراد الانضمام فليفعل

برافوا عليك يا مازن هذا ما سنفعله حقا

احب الشباب المتحمس ولكن همسه في الاذن ولكن نصيحة ابتعد عن كلمات مثل تحد لانها تنفر الشباب الخبراء

romanof كتب:

بالمناسبة من منطقة من اليمن انت ؟

و هذا حلي المقترح للسؤال، و الـ Overall complexity هي (θ(n

C# Code

void splitArray(int[] array)
{
	// ~~~~~~ Another fine solution by M@ZEN ~~~~~~

	//------------------------------------------------
	// For complexity evaluation, set n = array.length
	//------------------------------------------------

	// Variables declaration
	//----------------------
	int sum  = 0;
	int tsum = 0;
	int r1   = 0;
	int r2   = 0;

	int[] arr1 = new int[array.Length];
	int[] arr2 = new int[array.Length];

	// First Pass: sum array elements, O(n)
	//-------------------------------------
	for (int i = 0; i < array.Length; i++)
	{
		sum += array;
	}

	// Check if the array is splitable or not,
	// by checking if sum is even.
	//----------------------------------------
	if (sum % 2 != 0)
		return;

	sum /= 2;

	// Second pass: split the array, O(n)
	//---------------------------------
	for (int i = 0; i < array.Length; i++)
	{
		if (tsum + array <= sum)
		{
			tsum += array;
			arr1[r1++] = array;
		}
		else
		{
			arr2[r2++] = array;
		}
	}

	// Check if whether the array is correctly splitted or not,
	// by checking if tsum equals sum
	//--------------------------------------------------------
	if (sum != tsum)
		return;

	// Output, O(n)
	//-------------
	for (int i = 0; i < r1; i++)
		Console.Write(arr1 + " ");

	Console.Write("\n");

	for (int i = 0; i < r2; i++)
		Console.Write(arr2 + " ");

	//------------------------
	// Overall complexity θ(n)
	//------------------------
}

لم افحص جميع الحلول يا شباب ولكن اريد ان اوضح نقطة قبل ان اقبل الحلول ليس من الضروي ان يكون عددد العناصر في المجموعتين متساوين مثلا

فان

حل مقبول

حل مقبول المهم ان يكون مجموع العناصر في المجموعة الجزئية الاولى والمجموعة الجزئية الثانية متساويا

وعليه اذا كان هناك من لم يا خذ هذا الامر بعين الاعتبار فحله خطا

يا ساتر باين عمري ما بلاقي وضيفة...

:blink: :P :wacko: :s :(

يا صليحي اتق الله ماهذه درجة التعيقد الكبير هل يمكن ان تبين كيف وصلت الى هذه النتيجة ؟

 for (int i = 0; i < array.Length; i++)
	{
		if (tsum + array <= sum)
		{
			tsum += array;
			arr1[r1++] = array;
		}
		else
		{
			arr2[r2++] = array;
		}
	}

اعتقد ان الخطا هنا يا مازن

هل تريدون كتابة الخوارزمية مع الكود ؟؟ أم مجرد الخوارزمية فقط ؟؟؟

والله اشرح لنا الخوارمية وبعدها مو مشكلة

هل يوجد غموض في الخوارزمية التي قدمتها ؟

خوارزمية جميلة يا أخ informat أحييك ولله. ناقص نعملها test علشان نتأكد من صحتها.

نعم

الخوارزمية التي لا تعمل جربها على

نحن لا نعرف اذا كان العدد الثاني والاول سيكونان في نفس المجموعة فهمتني !

وربما كانت المجوعة الاولى فيها الاول والثالث والرابع

اضف الى ذلك قمت بعناء ترتيب العناصر

شكراً على المتابعة أخي romanof

لم أجد حلاً سوى باستخدام الـ Best First Search

المشكله هي أن الـ Complexity تساوي (!O(n

/// C# CODE ///

		static void splitArray(int[] array)
		{
			// ~~~~~~ A fine(r) solution by M@ZEN ~~~~~~
			int sum  = 0;

			for (int i = 0; i < array.Length; i++)
				sum += array;

			if (sum % 2 != 0)
				return;
			sum /= 2;

			// BFS, O(n!)
			//-----------
			State init	 = new State(sum, new int[1] {array[0]}, 
							 State.removeElemnt(array, 0) );
			State current  = init;
			Queue<State> q = new Queue<State>();

			q.Enqueue(init);
			while (!current.isGoal() && !(q.Count == 0))
			{
				current = q.Dequeue();
				State[] ex = current.expand();

				foreach (State s in ex)
					if( s.isValid() )
						q.Enqueue(s);
			}

			if (current.isGoal()) current.output();
			else Console.Write("Array is NOT splitable under required conditions.");

			//-----------------------------
			// Overall complexity O(n!) =D
			//-----------------------------
		}

		public class State
		{
			int [] activeComb;
			int [] rest;
			int mean;

			public State( int _mean, int [] _activeComb, int[] _rest)
			{
				mean = _mean;
				activeComb = _activeComb;
				rest = _rest;
			}

			public State[] expand()
			{
				State[] ret = new State[rest.Length];

				for (int i = 0; i < rest.Length; i++)
				{
					int[] newActiveComb = new int[activeComb.Length + 1];
					int[] newRest = removeElemnt(rest, i);

					Array.Copy(activeComb, newActiveComb, activeComb.Length);
					newActiveComb[newActiveComb.Length - 1] = rest;

					ret = new State(mean, newActiveComb, newRest);
				}

				return ret;
			}

			public bool isGoal()
			{
				int tsum1 = 0, 
					tsum2 = 0;

				for (int i = 0; i < activeComb.Length; i++)
					tsum1 += activeComb;
				if (tsum1 != mean)
					return false; 

				for (int j = 0; j < rest.Length; j++)
					tsum2 += rest[j];

				if (tsum2 != mean)
					return false;

				return true;
			}

			public bool isValid()
			{
				int tsum1 = 0,
					tsum2 = 0;

				for (int i = 0; i < activeComb.Length; i++)
					tsum1 += activeComb;
				if (tsum1 > mean)
					return false;

				for (int j = 0; j < rest.Length; j++)
					tsum2 += rest[j];
				if (tsum2 < mean)
					return false;

				return true;
			}

			public static int[] removeElemnt(int[] arr, int i)
			{
				int[] ret = new int[arr.Length - 1];
				int index = 0;

				for (int j = 0; j < arr.Length; j++)
				{
					if (j == i) continue;
					ret[index++] = arr[j];
				}

				return ret;
			}

			internal void output()
			{
				for (int i = 0; i < activeComb.Length; i++)
					Console.Write(activeComb + " ");
				Console.Write("\n");

				for (int i = 0; i < rest.Length; i++)
					Console.Write(rest + " ");
				Console.Write("\n");
				Console.Write("\n");
			}
		}

اخي مازن هلا شرحت الخوارزمية قبل ان تضع الكود

عموما الحل بسيط بما اننا نمتلك مجموعة تحتوي على n عنصر فان عدد المجوعات الجزئية يساوي

واذا استثنينا الموحوعة الخالية والمجموعة الكلية (المجموعة الكلية هي المجموعة التي تحتوي على جميع العناصر )

فان عدد المجموعات الجزئية بساوي

والان سوف نحصل على كل المجموعات الجزئية ويكون الحل كالتالي

اذا كان A هي المجموعة الكلية

وكانت A1 هي المجموعة الجزئية فان A2 تساوي المتممة اي A\A1

اعتقد الى هنا مفهوم والان كيف كيف سنحصل على A1 ؟

انظر :

 for i:=1 to m do

1- نحول i الى عدد ثنائي ونضع الناتج في مصفوفة طولها=طول المصفوفة الاصلية يعني n

مثلا في المثال السابق

فان n=5

وعندما i=6

2-اذا ناخذ العناصر من A والتي نظائرها في b تساوي واحد ونضعها في مجموعة واحدة بحيث تشكل A1

ويقية العناصر نضمها الى A2

اذا عندما i=6 فان

  sum:=0;
  for i:=1 to n do
   if(b=1 ) then
	sum:=sum+a;

ا

اعتقد ان الامر اصبح واضح الان

الصعوبة كانت تكمن في ايجاد طريقة تسمح لنا بانتقاء عنصر ومرة 2 ومرة 3 بنفس الخوارزمية

لاحظ ان انك كل مرة تحصل على عنصرين مختلفين وكل مرة ثلاثيات مختلفة

وطبعا هذا يعود الى كون التمثيل الثنائي لاي عدد يختلف عن الاخر حتى اذا تشابه فيهما عدد الوحدات

تحياتي يا مازن بالمناسبة اذا لم اكن مخطئا فتعقيد الخوارزمية

هو

romanof كتب:

1- نحول i الى عدد ثنائي ونضع الناتج في مصفوفة طولها=طول المصفوفة الاصلية يعني n

بالنسبة للحل الذي اتبعته فاستخدمت Blind search algorithm و هي breadth first search ( كتبت خطأ بالأعلى best ).. آخر حل للمشاكل التي أجدها لا تحل :lol:

فكرة الحل هي أن نبدأ من state معينه بحيث تحتوي a1 عنصراً من a و a2 بقية العناصر. في الـ while نفحص ما إذا كانت الـ state هي الهدف أم لا، إذا لم تكن الهدف نولد جميع الاحتمالات الممكنة من الـ state الحالية (و ذلك بوضع عنصر من a2 في a1، لجميع العناصر في a2)، و نضعها في queue (مبدأ الـ Breadth first search). ثم نسحب أول عنصر من الـ queue و نطبق عليه جميع ما ورد.. هكذا حتى نجد الهدف أو إلى أن تتفرغ الـ queue. بغض النظر عن محتويات كل function في الحل الذي أوردته فإن أسماء الـ funcions تشكل تلخيصاً-abstraction لعملها.

و إلى مشكلة أخرى..

السؤال الثاني:

اكتب خوارزمية تقبل قيمة m ( حيث m بين 1 و 1000000، شاملة العددين ) و تطبع قيمتين: القيمة الأولى تمثل آخر رقم غير صفري في أقصى يمين القيمة !m، تتبع بعدد الأصفار على يمين ذلك العدد.

مثلاً: !10 يساوي 3628800، لذا ستكون القيم الطبوعة هي 8 و 2.

يبدو انك استخدمت احد الطرق المشهورة في عالم الخوارزميات

ما ان تذكر الbreadth first search الا وتذكرمعها الDepth-first search

عموما ما علبنا

اليك الخوارزمية

1-تدخل العدد m

2- نحسب مضروب m

3-

طبعا اذا كان m عدد اقل من الخمسة فلا داعي للتجريب لانه لن يكون هناك صفر 
  n= m!
  i=0
  k=0;
  while(n mod 10=0)   do
	 begin
	   i=i+1;
	   n = n div 10  
	   k=  n mod 10
	 end

ويهذا نكون قدحسبنا عدد الاصفار واخذنا الناتج اول رقم بعد الاصفار

 write(k);
  write(i);

فائق التحيات يا مازن

هل اضع بدوري خوارزمية للحل ؟

romanof كتب:

2- نحسب مضروب m

أكبر مشكله - أخي romanof - في هذا السؤال هو أن الـ input يصل إلى الـ 1000000، و لا يوجد - حسب علمي - نوع-type يستطيع تخزين قيمة كبيرة مثل !1000000 (إذ أن هذا المضروب يتكون من ~5.5 مليون رقم!). لذلك لا بد من طريقة أخرى لحل هذه المشكلة دون الاضطرار لحساب قيمة مضروب العدد المدخل.

تحية؛

اظن اني توصلت للحل بواسطه Recorsive operation

واما الفعاليه فهي O-n لا اكثر كما انه كان بأمكاني النزول الى اقل من هذا الا انني قررت الاكتفاء به خصوصا وانه ليس كبير بل عادي !

اما بالنسبه للحل فهو كالتالي :

1- اذا المصفوفه تملك رقمين ضع كل رقم في قسم واحد في A واخر في B

2- اذا المصفوفه تملك اكثر من رقمين

2.1 خذ رقم من المصفوفه وضعه في Temp

2.2 اعد تشغيل اللوجريتم على المصفوفه الجديده

2.3 اذا كان ( مجموع ما في القسم A والعدد Temp ناقص مجموع ما في B < مجموع ما في لآ والعدد Temp ناقص مجموع A)

2.3.1 ضع العدد في المجموعه A

2.4 اذا لم تنفذ الشرط 2.3 ضع العدد في المجموعه B

يمكنكم تجربت هذا اللوجريتم واظن انه لوجريتم جيد بالنسبه للمشكله المعروضه اما بالنسبه للكود فأنا كتبته بلغه باسكال يمكنكم تشغيله ورؤيه النتائج :

program Solution;
{ Edited By Nadeem , 10,08,06 }
{ Program which divide one group into 2 that have the same sum }
const Max = 10;
type arraytype1=array [1..Max] of integer;
	 arraytype2=array [1..(Max-1)] of integer;
var
i:integer;
Group:arraytype1;
A:arraytype2;
B:arraytype2;
 { This funtion get how many numbers still in array (non numbers we mark
   as zero because it will not change any thing in this problem O(n)) }
 function getarraystill(Group:arraytype1):integer;
  var
   i,still:integer;
  begin
   still:=0;
   for i:=1 to Max do
	 if (Group<>0) then still:=still+1;
   getarraystill:=still;
  end;
 { This procedure get the first number founded in group1 and put him in
 A and the second he found in B O(n) }
 procedure put(var Group1:arraytype1; var A,B:arraytype2);
  var
   i:integer;
   AClean:boolean;
  begin
   AClean:=true;
   for i:=1 to Max do
	begin
	 if (AClean) then if (Group1<> 0) then
	   begin
		AClean:=false;
		 A[1]:=group1;
		 group1:=0;
	   end;
	 if not(AClean) then if (group1<>0) then
	   begin
		 B[1]:=group1;
		 group1:=0;
	   end;
	end;
  end;
 { getting sum of an array O(n) }
 function getsum(A:arraytype2):integer;
  var i,sum:integer;
  begin
   sum:=0;
   for i:=1 to (Max-1) do sum:=sum+A;
   getsum:=sum;
  end;
 { The main divide procedure which make it by recorsive solution }
 procedure Divide(var Group:arraytype1; var A,B:arraytype2);
  var
   T:boolean;
   i,Temp:integer;
  begin
	i:=1;
	if (getarraystill(group))=2 then put(group,A,B)
   else
	begin
	 Temp:=0;
	 while (Temp=0) do
	  begin
	   if group<>0 then
		begin
		 Temp:=group;
		 group:=0;
		end;
		i:=i+1
	  end;
	  Divide(Group,A,B);
	  i:=1;	 T:=true;
	  if (ABS(getsum(A)+Temp-getsum(B)) <= ABS(getsum(B)+Temp-getsum(A))) then
		 begin
			while (T) do
			 begin
			   if A=0 then
				begin
				 A:=Temp;
				 T:=false;
				end;
			   i:=i+1
			 end;
		 end
		else
		 begin
			while (T) do
			 begin
			   if B=0 then
				begin
				 B:=Temp;
				 T:=false;
				end;
			   i:=i+1
			 end;
		 end;
	end;
  end;

begin
{ Filling the Group A,B with zero O(n) }
for i:=1 to (Max-1) do
  begin
   A:=0;
   B:=0;
   writeln('The ' ,i,' number of the group:');
   readln(group);
  end;
 writeln('The ' ,max,' number of the group:');
 readln(group[max]);
  divide(group,A,B);
 writeln('********************************************************');
 for i:=1 to (max-1) do
   begin
	writeln('The ',i,' number in A',A:5,' and in B ',B:5);
   end;
end.

حساب عدد الاصفار سهل لان عدد الاصفار يساوي عدد الخمسات الداخلة في عملية الضرب

لاحظ ان الصفر ظهر في الناتج فقط عندما دخلت 5 في الناتج مضروب 5 = 120

بينما مضروب 10 = 3628800

 K:=0;

  FOR I:=1 TO M do
	BEGIN
	   N:=I;
	   while( n mod 5 = 0)
		  begin
			k := k+1;
			n := n div 5;
		  end;  
	END;

العدد k يعطينا عدد الاصفار في مضروب m

وصلت الى الحل يا عزيزي يا مازن

لن تحتاج الى حفظ العدد كاملا سنتحتاج فقط الى رقم بعد الاصفار في كل مرة

ساعطيك مثال

نحتاج فقط الى 2 وبالتالي 6*2 = 12

اذا اول رقم يعد الاصفار = 2 في مضروب 6

والان 7*2 = 14 اذا اول رقم بعد الاصفار في مضروب 7 =4

لاحظ ان اول رقم بعد الاصفار هو 4

نستطيع ان نوكد ان اول رقم بعد الاصفار هو 2 لان 4*8 =32

اعتقد ان الامر وضح الان

اما كيفية الحصول على اول رقم بعد الاصفار امر بسيط

 
  repeat
   p = n mod 10;
   n = n div 10;
  until ( p <> 0 ) ;

romanof كتب:

حساب عدد الاصفار سهل لان عدد الاصفار يساوي عدد الخمسات الداخلة في عملية الضرب

لاحظ ان الصفر ظهر في الناتج فقط عندما دخلت 5 في الناتج مضروب 5 = 120

بينما مضروب 10 = 3628800

أحسنت أخي romanof :)

undefined

romanof كتب:

وصلت الى الحل يا عزيزي يا مازن

لن تحتاج الى حفظ العدد كاملا سنتحتاج فقط الى رقم بعد الاصفار في كل مرة

طريقة صحيحة، و حدس رياضي ;) و لكنني لم أستطع ربط الـ code المرفق بالـ code الأول؛ و يا حبذا لو تكتب كامل الخوارزمية.

في حفظ الله؛