مسأله عقدتني

السؤال غير واضح بالنسبة لي ..

اسفة يمكن من السكانر طلع غير واضح :)

سأعيد كتابة السؤال

given an array L[1...n] of non negative real numbers,, we want to find the max product realizable as the product of contiguous subsequence of numbers of L,, for example
if L={0.6, 0,23, 0.5, 28, 0.9}   the answer is 322=23*0.5*28
if L={0.8, 0.9, 0.6} the answer is 0.9
if L={1, 0, 12, 3, 1, 2, 0.001, 39}   the answer is 72=12*3*1*2

write an O(n) algorithm to solve the problem ,,,

السؤال اخى حسن هو كالتالى:

لديك سلسله من الارقام حاول الحصول على اكبر رقم ممكن بضرب مجموعه من الارقام المتسلسه فى هذه السلسله, المشكله ليست فى السؤال إنما هو ان السؤال به شرط والشرط هو ان لا يتجاوز وزن البرنامج سرعة (O(n.

تستطيع ان تقول ان المطلوب بشرط ان لا تستخدم حلقتين داخل بعض, او عدم إستدعاء حلقه او داله من داخل حلقه.. هذه طبعاً ليست كل الشروط ولكن حبيت بس اقرب الموضوع للاخوه الذين لم يتعاملو بعد معى المسطلح Ordo او Big O كما يطلق عليها.

اعتقد ان مثل هذه الاسئله لابد من مناقشتها اولاً قبل الوصول للحل الصحيح, على ما اذكر كنا نستخدم ما يسمى بالـDynamic Search لحل مثل هذه المسائل ولكن للاسف لم استخدم هذه الطريقه منذ زمن, لذلك على ان ارجع للكتب القديمه وإن شاء الله إذا لم يستطع احد ان يساعدك احاول ان اقراء بعض المراجع التى عندى واعود.

والسلام عليكم

أخوي أحمد غريب

أشكرك لإهتمامك :)

كلامك صحيح ... يجب استخدام loop واحدة من 1 الى n

والحل الأنسب هو dynamic programing كما تفضلت ... أتمنى من لديه خبرة ف هذا المجال أن يفيدني بعض الشئ ف وقت قريب ..

لأنني في أشد الحاجة الى التوصل الى حل ..

دمتم بخير

اختكم

دارك

ادخل هذا الرابط واقرا الكتا ب ذو الاسم

Intro to Algorithms.pdf

رغم اني انصحك بالقيام بقرءة الكتابين الاولين ثم المذكور اعلاه

/index.ph...e=post&id=12247

romanof

اشكرك اخي الفاضل ...

أنا لدي كتاب :)

استشرت دكتوري ف الجامعة ... ووجدت هذا الحل

سأضعه هنا للفائدة :)

The solution is: 
INPUT (L:  array L[1..n])
OUPUT MAXPRODUCT

We first declare:  Product  as an  array [1..n];

{ product[1]= L[1];
  for (int k=2;k<=n;k++)
        product[k] = max(L[k], product[k-1] * L[k]);

   Then, we complete the algorithm by passing through product and returning  the maximum value.
}

ممم .. ما المقصود بـ dynamic programing ؟

اقتباس

 for (int k=2;k<=n;k++)
       product[k] = max(L[k], product[k-1] * L[k]);

و لكن هذا يحسب فقط سلاسل طولها عنصرين .. ماذا لو كان اكبر عنصر هو في سلسلة طولها ثلاث عناصر؟

كما انه لا يبد dynamic بالنسبة لان كل الحالات اصحبت hard coded

max(L[k], product[k-1] * L[k])

يعني ممكن ايضا ناخذ

max(L[k], product[k-1] * L[k], product[k-2] *product[k-1] * L[k] )

عموما نا بصراحة لم افكر كثيرا في الموضوع لذلك ربما هناك اخطاء واضحة في كلامي (لا ادري)

السلام عليكم

بالفعل نفس الفكره التى كانت عندى يا اخت دارك ولكن كنت افكر فى مشكلة الذاكره, هذه الطريقه تستهلك الذاكره بشكل كبير ولكنها ايضاً سريعه جداً فى حساب مثل هذه الانواع من المشاكل..

اخى حسن الDynamic Programing تستخدم فى العثور على سلسله من الحلول فى سلسله من المعطيات, لو لاحظت حل الاخت دارك ستجد انها بهذا الحل تحصل على مجموعه كبيره من الحلول ثم فى سلسله جديده تختار اكبر حل من الحلول التى حصلت عليها. العلاقه

اقتباس

max(L[k], product[k-1] * L[k], product[k-2] *product[k-1] * L[k] )

موجوده ضمن الحلول حاول التعمق فى حل الاخت دارك وسوف تلاحظ انه يحمل جميع الحلول ما عدى الحلول التى نعرف بالضروره اصغر من غيرها.

يمكنك إختبار الخوارزميه بمعطيات مثل {½,1,2,½,3,4}

ونجد النتيجه التاليه :

product[1]=3
product[2]=product[1] * 4=12
product[3]=product[2] * ½=6
product[4]=product[3] * 1=6
product[5]=product[4] * 2=12
product[6]=product[5] * ½=6

والان لدينا سلسله من النتائج ويمكننا بالمقارنه تحديد الرقم الاكبر وهو 12 فى هذه الحاله ...

ارجو ان تكون الصوره وضحت الان..

والسلام عليكم

السـّلام عليكم

اعتقد الحل أبسط من حلك ’

لاأدري قد لاأكون فهمت السؤال جيداً ولكن لك محاولتي

,

تستطيـع ايجاد الماكس بBig O (n) بدون أي تريك معين .

فقط تركز على عمل عمليه معينه او expression

ان لاتتعدى ال n مره . .

int max=L[0];
for(int i=1;i<n;i++)
if(L>max)
max=L;

مثلاً هنا عملية الi<n نفذت n مره . .

فهمت السؤال غلط اخى عيسى نحن هنا لا نبحث عن اكبر عدد وإنما نبحث عن اكبر عدد يمكننا الحصول عليه بضرب اعداد متتاليه داخل الArray حلك كان يكون صحيح إذا كان السؤال عن اكبر عدد فى السلسله.

شكراً اخي احمد

هذا هو الحل

#include<iostream>
#include<cstdio>


int main()
{
	float list[]={5,7,0.2,8,float(1)/7};
	float pro = list[0];
	float temp = list[0];
	for(int i=1;i<5;i++)
	{
  pro *=list;
  if(pro > temp)
 	 temp = pro;
  if(temp < list)
 	 temp = list;
  if(pro == 0 )
 	 pro = 1;

	}
	std::cout<<"PRO = "<<temp<<"\n";

}

الحل فيه خطاء منطقى خطير يا bms حاول ان تطبق الخوازميه التى كتبتها فى المصفوفه التاليه مثلاُ

[10,0.5,20]

ستلاحظ ان الناتج الذى ستحصل عليه بإستخدام هذه الخوارزميه هو 20 فى حين ان الحل الصحيح فهو 100..

والسلام عليكم

اخوي احمد غريب هل هذه الملاحظة استنتجتها بدون ما تطبق الكود ؟

لاني مطبقه بالمثال اللي حطيته وطلع معي الحل صح 100

بس لاحظ عدد التكرار يتغير على حسب عدد عناصر المصفوفة يعني في مثالك راح يكون 4

السلام عليكم

انا اسف الظاهر مخى انا إلى فيه خطاء منطقى, على كل حال حلك برضو غير سليم, المشكله بكل بساطه هى انك فى الDynamic programming يجيب ان تضحى بالمساحه لتكسب الوقت, ولكن برنامجك لا يضحى بالمساحه لانه يستخدم متغيرين اثنين فقط..

والان جرب هذا المثال وسترى ان الحل ينقصه شيئ.

[0.2,0.5,10,5]

المفروض الناتج يكون 50 جرب برنامجك ستلاحظ ان الناتج يساوى 10.

وفعلاً انا لم اجرب البرنامج إنما هو إستنتاج بدون تطبيق الكود لانى للاسف لا املك مترجم سى ..

والسلام عليكم

اخوي احمد غريب ملاحظتك صحيحة والظاهر إني ما أنتبهت

لهذه الحالة على العموم التعديل بسيط جدا وهو إضافة سطر واحد فقط

وهذا الكود بعد التعديل

#include<iostream>
#include<iomanip>


int main()
{
	float list[]={7, 5 , 0.2 , 8 , 1.0/7.0};
	float pro = list[0];
	float temp = list[0];
	for(int i=1;i<5;i++)
	{
  pro *=list;
  if(pro > temp)
 	 temp = pro;
  if(temp < list){
 	 temp = list;
 	 pro = temp; //  هذا هو السطر المضاف فقط 
  }
  if(pro == 0 )
 	 pro = 1;

	}
	std::cout<<"PRO = "<<temp<<"\n";

}

وحبيت انبه اني ما أعرف مبادئ dynamic programming عشان ابرمج فيه ^_^

وبإنتظار ملاحظاتك وشكرا

السلام عليكم

اخى bms طبعاً انا معجب جداً بمحاولاتك ولكن مثل هذه المسئله مستحيل ان تحل بدون إستهلاك ذاكره, وعلى فكره إذا استطعت ان تصل إلى حل لايستهلك الذاكره ربما تكون جائزه نوبل للفيزياء من نصيبل المره القادمه..

جرب المصفوفه التاليه وستجد ان الحل غير سليم..

{100.0, 0.0 , 0.1 , 100.0 , 100.0}

الحل بالطبع هو 10000 ولكن البرنامج سيكتب 1000 يعنى لا تتعب نفسك اخى علماء الرياضيات حاولو كثيراً حل هذه المشكله بدون إستخدام الdynamic Programming ولم يفلحو, لا بد ان تحتفظ بجميع الحلول فى مصفوفه ثم تقارنها ببعض وإلا لن تصل للحل الصحيح..

طبعاُ انا تعبت حتى وجدت المثال الذى يثبت الخلل فى الخوارزميه التى كتبتها ولكن لم اكن لاحاول لو لم اكن واثق من انه لايوجد حل مباشر لهذه المسئله..

والسلام عليكم

اخوي احمد قريت ال dynamic programming ونزلت صفحات فيها وقريتها وعرفت الفكرة الي هي

قائمة عليها بس ما أظن هذا السؤال ماله حل إلا بهذه الطريقة شوف هذا الكود هو نفسه الكود السابق أي الحل الصحيح اللي في الصفحة اللي قبل

مع تعديل بسيط (( على إعتبار الحل السابق حق العضو dark_angle هو الحل الصح ))

float max1(float list[], const int n)
{
	float * pro = new float[n];

	pro[0] = list[0];
	float max = pro[0];

	for(int k=1; k<n; k++)
	{
  pro[k] = max(list[k] , list[k] * pro[k-1]);
  if(pro[k] > max )
  	max = pro[k];
	}
	delete []pro;
	return max;
}

لاحظ إن المصفوفة اللي أنشأنها ما نستخدم منها إلا أخر خانة وأكبر رقم نحطه في المتغير max وعلى كذا ما راح نحتاج نمر على المصفوفة

مرة ثانية .

بهذه المعلومة تقدر نغير الكود ليصبح ما يستهلك أي ذاكرة مالها داعي وهذا هو الكود بعد التعديل

float max2(float list[] , const int n)
{
	float pro = list[0];
	float temp = list[0];
	for(int i=1;i<n;i++)
	{
  pro *=list;

  if(list > pro )
  	pro = list;

  if(pro > temp)
  	temp = pro;

  if(temp < list)
  	temp = list;

  if(pro == 0 )
  	pro = 1;

	}
	return temp;

}

وابانتظار ملاحظاتك أخوي احمد وإن شاء الله مافي غلطات وحبيت انبه ان الطريقتان حطيتهم في برنامج ووضعت ارقام عشوائية في حلقة تكرار

بعدد مليون ثم جربته مرة ومرتين وثلاثة ولا مرة طلع فيه اختلاف والهذا البرنامج لمن أراد أن يطلع وضعته مع الملف المرفق

وأخيرا مشكور أخوي أحمد على المعلومات اللي اتسفدتها منك يمكن يكون حلي صح واستاهل جائزة نوبل ^_^

والسلام عليكم ورحمة الله وبركاته

product.txt

السلام عليكم

اقر واعترف انا الموقع ادناه اننى كنت مخطاء فى تحليل المسئله فهى لا تحتاج إلى dynaminc programming وبذلك لن تستهلك الذاكره كما ادعية سابقاً..

كلامك سلم يا bms عادة فى الdynamic programming يكون الشرط اعقد من مجرد إظهار max كما هو الحال فى هذه المسئله حيث انه لا تستطيع التخلص من النتائج إلا بعد مقارنتها, اما فى هذه الحاله كانت المقارنه بسيطه لذلك لم نكن بحاجه لإستخدام dynamic ....

نصيحه بسيطه اخى bms حاول ان تعتمد على التحليل المنطقى اكثر من التجارب المباشره, لانك حتى لو قمت بتجربة الخوارزميه مليون مره فربما يكون هناك إختلاف فى المليون و واحد مره. طبعاً التجربه العمليه مطلوبه ولكن لايجب الاعتماد عليها كمصدر اساسى للنتيجه النهائيه. انا لا املك كمبايلر سى وكان إعتمادى فقط هو تحليل الشفره وتحويلها إلى خوارزميه مقروئه حتى اتابع ما يحدث, وإن شاء الله اقوم بتنصيب كمبايلر عن ما قريب..

اشكر اخى bms على هذا الموضوع المميز الذى اثريته بمداخلاتك القويه...

للاسف جائزة نوبل ليست بالامر الهين, ربما لو اوجدت حل لمشكله Traveling Salesman Problem تحصل عليها..

والسلام عليكم