الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

خوارزمية إيجاد المنوال بتعقيد أقل

بدأه aohammed في 12 يوليو 2010 · 7 رد · 2,761 مشاهدة · في الرياضيات والخوارزميات
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

السلام عليكم

المنوال في الاحصاء : هو القيمة الأكثر تكرارا ً بين مجموعة أرقام

يمكن أن يكون قيمة أو قيمتين و أكثر أو لا شيء

قمت بكتابة الكود التالي بلغة c++

و عالجت جميع الحالات الخاصة

لكن لاحظت أن تعقيدها2^n و ذلك في أسوء حالاتها ( حالة عدم وجود منوال)

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

هذا هو الكود

#include "stdafx.h"
#include<iostream>
using namespace std;
void main()
{
const int size=4;
int a[size]={1,2,3,3};
int index=0;
int lastindex;
int max=a[0];
int maxCounter=0;
int lastmaxCounter;
int i;
int rep=1;
for(i=0;i<size;i++)
{
	if(a==max)
	{    	
    	++maxCounter;
    	lastindex=i;
	}
if(i==(size-1) && maxCounter<((size)-(lastindex)))
{
	i=0;
	++index;
	max=a[(index)];
	if(lastmaxCounter==maxCounter+1 && index!=0)
	{
    	rep++;
	}
	lastmaxCounter=maxCounter+1;
	maxCounter=0;

}

}

if(maxCounter==1)
cout<<"There is No Number Repeater in This matrix";
else if(maxCounter==size/(rep+1))
{
	cout<<"There is "<<(rep+1)<<" Frequenset\n";
	for(int c=0;c<size;c+=maxCounter)
	{
    	cout<<a[c]<<"\t";
	}
}
else
cout<<max<<"\t"<<maxCounter;


}

ملاحظة الـ max هو متحول المنوال

#2

اعتقد انه توجد خوارزمية اسرع تعمل في وقت خطي 

O(n)

راجع الموضوع المثبت كورس خوارزميات او كتاب Cormen

تم تعديل هذه المشاركة بواسطة ibr_exn في 12 يوليو 2010 في 17:44

الحمد لله الذي هدانا لهذا وماكنا لنهتدي لولا ان هدانا الله

#3

لازلت أنتظر إجابة :( مع الشكر

#4

أحسن تعقيد فكرت فيه هو n*logn + n

وهو بترتيب العناصر أولاً ثم البحث عن العنصر الأكثر تكراراً

أحب أن أعرف الخوارزمية التي تتكلم عنها أخي إبراهيم :)

تحياتي

حزمة المحرك الإصدارة 0.8

أي أحد يجد أني ظلمته فليراسلني

وبإذن الله لو كان له حق سيأخذه

728x90.png

#5

احم احم

وجدتها

يمكنك استخدام Hash table

لحل المشكلة بتعقيد أقل إذا ضمنا عدم حدوث الـ collision أو قلته

تحياتي

حزمة المحرك الإصدارة 0.8

أي أحد يجد أني ظلمته فليراسلني

وبإذن الله لو كان له حق سيأخذه

728x90.png

#6
اقتباس
وجدتها

يمكنك استخدام Hash table

لحل المشكلة بتعقيد أقل إذا ضمنا عدم حدوث الـ collision أو قلته

ممكن كود أو خوارزمية؟

مع الشكر

#7

أخي هل تعرف Hashtable?

اقرأ عنها بشكل جيد

على العموم في جافا هناك فئة تعمل بشكل جيد لها

حاول أن تكتب الشيفرة وسأساعدك

تحياتي

حزمة المحرك الإصدارة 0.8

أي أحد يجد أني ظلمته فليراسلني

وبإذن الله لو كان له حق سيأخذه

728x90.png

#8
اقتباس
المنوال في الاحصاء : هو القيمة الأكثر تكرارا ً بين مجموعة أرقام

يمكن أن يكون قيمة أو قيمتين و أكثر أو لا شيء

عذرا لم أفهم هذه النقطه :)

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

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

================

يمكن ايجاد المنوال في زمن خطي O(N) Linear Time اذا كان مدى العناصر معروف مسبقا و صغير الى حد ما كالتالي

Input: Array A, Size of the array (n)

Output: Print the most recurring elements or create a list of them

Algorithm:

1. Create an array C of size of the range of elements
for example, if the elements in the array range from 0x0000 to 0xFFFF then create array C of size 0xFF

2. Loop through all elements in the array making all of them zeros

for(i = 1; i <= Range; i++)
	C = 0

3. Count the occurence of every value found in array A into array C => O(N) time

for(i = 1; i <= Size; i++)
	C[A] = C[A] + 1

4. Find the maximum value k in C => O(N) time

5. Loop through the array C and print the index of any element with value k or add it to a list

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

مواضيع مشابهة