ملتقى طلاب الاعلام الالي لحل تمارين Algorithmes et programmation en Pascal

[بهاار]

شكرا لك اخي انا في البسكال لم تنجح
لكن قمت بفتح ملف البسكال ب bloc note واضفتها

[you92cef]

المشاركة الأصلية كتبت بواسطة بهاار

شكرا لك اخي انا في البسكال لم تنجح
لكن قمت بفتح ملف البسكال ب bloc note واضفتها

بحسب نسخة الباسكال التي تستخدمها
الطريقة شغالة على نسخة tpw

[بهاار]

السلام عليكم

من فضلكم اريد شرح لطريقة ترتيب جدول بطريقة شل
انا وجدت procedure لكن لم افهمها

  procedure tri****l (var t:tab; n:integer ) ;
   var    p,i,j,v: integer;
   begin    
       p:=0;
       while p<= n do    
       p:= 3*p+1;
       while p <> 0 do
        begin
            p:=p div 3;
            for i:= p to n do
             begin
                  v:=t[i];
                  j:=i;
                  while (j > p-1) and (t[j-p] > v ) do
  begin
                        t[j]:=t[j-p];
  j:=j-p;
                   end;
                  t[j]:=v;
             end;
        end;
   end;

[you92cef]

نتيجة الطريقة هي ترتيب جدول تصاعديا
ordre croissant
mais comment moi aussi je ne comprendre pas la maniere

program exe

program ex;
uses wincrt;
type tableau=array[1..100]of integer;
var tab:tableau;
j,m:integer;
procedure tri (var t:tableau; n:integer ) ;
   var    p,i,j,v: integer;
   begin    
       p:=0;
       while p<= n do     
       p:= 3*p+1;
       while p <> 0 do
        begin
            p:=p div 3;
            for i:= p to n do
             begin
                  v:=t[i];
                  j:=i;
                  while (j > p-1) and (t[j-p] > v ) do begin
                        t[j]:=t[j-p];  
                         j:=j-p;   
                   end;
                  t[j]:=v;
             end;
        end;
   end;
begin
writeln('Entrez m');
readln(m);
for j:=1 to m do begin
writeln ('Entrez tab[',j,']');
readln(tab[j]);
end;
tri(tab,m);
writeln('-----------------------');
for j:=1 to m do
writeln(tab[j]);
end.

[بهاار]

https://www.youtube.com/watch?v=wdrwwl5Ib9g

هدا يشرح قليلا الطريقة لكن الشي الذي لم افهمه انا

       
while p<= n do             p:= 3*p+1;        while p <> 0 do         begin             p:=p div 3;

[you92cef]

المشاركة الأصلية كتبت بواسطة بهاار

https://www.youtube.com/watch?v=wdrwwl5Ib9g

هدا يشرح قليلا الطريقة لكن الشي الذي لم افهمه انا

       
while p<= n do             p:= 3*p+1;        while p <> 0 do         begin             p:=p div 3;

الغوريتم شل هو تطوير لالغوريتم
tri par insertion
ولكن اسرع من
tri par insertion



موقع رائع لشرع انواع الترتيبات الممكنة
https://people.cs.pitt.edu/~kirk/cs15...ons/Sort1.html

يمكن اختيار نوع الترتيب ال>ي نريده من في الخانة الاولى ثم ندخل عناصر الجدول ونفصل بينهم ب
space
لفهم الاختلاف بين انواع الترتيبا ننصح باختيار عناصر جدول واحد مثلا
1 5 8 9 7 3 2 9 6 3 1 2
وكل مرة نغير طريقة ترتيب العناصر

ارجوا من الادارة عدم حدف الموقع لانه ليس اشهاري

[بهاار]

لكن الذي لم افهمه
لماذا p;=0
ومادا يقصد ب p
وبعدها لماذا p;=3*p+1

[you92cef]

في
tri par insertion
نقارن العنصر
i
مع العنصر الدي يليه
i+1
في هده الحالة نحتاج الى وقت كبير
----------------------------
بينما في شال
نقارن العنصر
p
مع
عنصر اخر لا يكون بالضرورة
p+1
فشال اول مرة حاء بالعبارة
p:=0
p:=3*p+1
ففي شال
دائما نقارن العنصر
p
ال>ي يكون في الاول يساوي 1
مع عنصر اخر شال عبر عنه ب
p:=p*3+1
ثم قسم على 3
يمكن ان نضرب مثلا في 5 ونقسم على 5 وهكدا نكسب وقت اكبر
--------------------------------------------
كمبرمجين ما يهمنا هو كيفية عمل البروسيدور والنتيجة وممزياته وعيوبه اما لمادا وكيف وباقي الاسئلة فهي اسئلة رياضية تدخل ضمن
recherche operationnelle
*-*تطبيق الرياضيات في الاعلام الالي او تطبيق الاعلام اللي في الرياضيات*-*
ou algo avanceé
وهده تحتاج الى فهم قوي ومتين بالالغوريتم والرياضيات

[بهاار]

المشاركة الأصلية كتبت بواسطة you92cef

فشال اول مرة حاء بالعبارة
p:=0
p:=3*p+1
ففي شال
دائما نقارن العنصر
p
ال>ي يكون في الاول يساوي 1
مع عنصر اخر شال عبر عنه ب
p:=p*3+1
ثم قسم على 3
يمكن ان نضرب مثلا في 5 ونقسم على 5 وهكدا نكسب وقت اكبر
--------------------------------------------

انا الشي الذي لم افهمه لماذا ضرب في 3 ثم قسم على3

يعني اين الفائدة لما اضرب في 3 ثم اقسم على 3

[بهاار]

  procedure ****l (n: integer ; var t:tab ) ;var    p,i,j,valeur: integer; begin         p:=0;     while p < n do         p:= 3*p+1;     while p > 0 do      begin          p:=p div 3;          for i:= p to n do           begin                valeur:=t[i];                j:=i;                while (j > p-1) and (t[j-p] > valeur ) do                 begin                      t[j]:=t[j-p];                      j:=j-p;                 end;                t[j]:=valeur;           end;      end; end;

والله لم افهم شي اخي الكريم ياريت لو تكرمت وكتبت لي تعليق بسيط امام كل instruction

[بهاار]

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

[you92cef]

الله يكون في العون لان ه>ه الخوارزميات الناس تخصص تعمل دوتوراه من اجلها وتتطرق لها من كل الجوانب لان الاعلام الالي ليس فقط البرمجة
----------------------------------
لغرض تنظيم المعلومات وترتيبها تم اكتشاف وابتكار خوارزميات من اجل هه>ا الهدف من بينها خوارزميات الترتيب
les algo de tri
من بينها كان لدينا
algo tri par insertion
حيث اننا نقارن القيمة الحالية مع القيمة التي تليها وهكدا
ولما نجد ان القيمة
i+1
اصغر من القيمة
i
علينا ان نغير من تريتب القيميتن
ثم نقارن مع القيم التي تلي قيمة i
مثلا
1 8 9 6 7 3 4 0
-*- القرائة من اليمين الى اليسار-*-
لدينا 1اصغر من 8
8اصغر من 9
9اكبر من 6-*- علينا ان نغير القيم
فتصبح هك>ا
1 8 6 9 7 3 4 0
الان علينا ان نقارن 6 مع 8 ايضا نعمل تغري بين القيمتين فتصبح هكدا
1 6 8 9 7 3 4 0
الان لدينا 9 اكبر من 7 نغير فتصبح
1 6 8 7 9 3 4 0
نقارن 7 مع 8 لا نغير
7 مع 8 لا نغير

لدينا 3 اصغر من 9
نغير قتصبح هك>ا
1 6 8 7 3 9 4 0
ونستمر ونستمر
حتى نصل الى الصفر فمع الصفر علينا ان نغيره مع القيمة التي تسبقه ثم التي تسبقه ثم التي تسبقه ...... حتى يصير في المرتبة الاولى
-*- مع المفروض اننا ننقلها مباشرة-*-

الجدير بالدكر ان كل عملية نقوم بها تحتاج الى وقت ومساحة في الداكرة
espace memeoire

لتفادي ه>ه المشاكل العالم شال اكتشف خوارزمية شال التي هي تعميم ل
tri par insertion
-*-le tri par insertion est un cas perticulier de tri

s h e l

lorsque on multiple par 1 est on devise par 1

كما نعرف ففي
tri par insertion
لا يمكننا تغير التريتب الى بمرتبة واحدة
ادا كان عنصر في المكان 2 فاما يصير في المرتبة 1 او يصبح في المرتبة 3
في كل مرة نحرك العنصر بمرتبة واحدة
لمادا؟
لاننا كما قلنا
le tri par insertion on multiple par 1 et on devive par 1

alors on peut que deplacer l'element d'une place

من اجل هدا شال اقترح انه يمكننا ربح لوقت ومساحةى الداكرة
gagner de temps et d''espace memoire

pour cela au lieu de multiplier par1 et deveiser par 1
on peut multiplyer par k est deviser par k
dans ce cas on ^peut deplacer un elemnt de k place
si k:=5
alors si un element a la place 6 alors
il peau etre sur la 1 ere place avec jusque un permutation *-* pas 5 permutation dans tri par insertion-*-
ou avoir la place 11 de meme maniere


من اجل عدة اسباب تتعلق بفعالية الخوارزمية وتتعلق بالوقت وبمساحة الداكرة من الافضل اختيار
un pas de 3
alors on * par 3
ensuite on / par 3
si par example
k<>1 ou k<>3 on n'est pas sur que on a les resulatat que on aime avoir
-*- il peut que le tableau u otre chz ne soit par tri par ordre croisant -*-
alors on perdre de temps e de ram pour r1
e il peut que si k e tres grand que on revien a un tri par inertion -*- ce qui on veut evider-*-

donc pour tout ca on multiple par 3 et / par 3

car aussi dans le cas ou le pas est 3 on ait sur que le pas va prendre la valeur 1 e donc on a un tri par insertion

le tri de shal passe toujours par tri par insertion lorsque le pas est 3 mais ce tri par insertion est organiser dons sa qsera plus rapide que le tri par insertion normale

La formule la plus couramment utilisée pour calculer la valeur des pas successifs est la suivante U(n+1)=(3Un+1) avec U0=0.


Lorsque le pas atteint la valeur 1, cela revient à effectuer le tri par insertion. Cependant, cette fois, le tri par insertion est appliqué à un tableau possédant un certain ordre (provoqué par les étapes de préparations où le pas est supérieur à un)

car le tri par insertion est efficasse qand on a un tableu a peut pré trieé


après une étape où le pas est de quatre, les quatre premières valeurs du tableau sont les quatre plus petites, les quatre suivantes sont plus grandes ext


En résumé, le tri ****l permet d’organiser plus rapidement le tableau à trier. donc gagner de temps est d'espac memeoire


Grandeurs successives de p pour n=100
Calcul du plus grande valeur de p tel que p<100 :
U0=0
U1=3U0+1=1
U2=3U1+1=4
U3=3U2+1=13
U4=3U3+1=40
U5=3U4+1=121
Conclusion : la plus grande valeur de p tel que p<100 est 40. Les valeurs successives du pas p seront alors : (ou la division par 3 est une division entiére).
p1=121/3=40
on peut deplacer l'element de 40place !!!!!
p2=p1/3=40/3=13
aussi de 13 place !!!!!
p3=p2/3=13/3=4
4 place !!!!!!
p4=p3/3=4/3=1
tri par insertion mais organiser car on deplace -*- si la valeur est plus grnd-* 40 place a la fois



Exemple de tri
ةvolution du tableau au fil du tri ****l. Le pas, représenté en rouge est également indiqué ainsi que la valeur en mémoire, sur laquelle porte la comparaison. En bleu, les valeurs sur lesquels portent les comparaisons à chaque étape.
--------------------

المثال في الصورة التالية مع الشرح


A ce stade, le tri fusion revient à effectuer le tri par insertion. L’exemple s’arrêtera donc ici. Il faut cependant remarquer que, grâce aux différentes étapes du tri ****l, le tableau est un peu mieux organisé : La moyenne des valeurs de la première moitié du tableau a diminué. Ce résultat est d’autant plus remarquable que le tableau à trier est grand.

لفهم اكثر راجع*-*ي-*-* الموقع السابق


***
تعني
شال
لم اكن اكتبها كتابة صحيحة لذلك قد يكون تغير معناه ونتج عنها ***


شكرا

[you92cef]

الموقع
https://people.cs.pitt.edu/~kirk/cs15...ons/Sort1.html

كيفية الاستخدام







شكرا

[بهاار]

بارك الله فيك

[بهاار]

من فضلك اخي الكريم ارجو ان تبين لي كيفية كتابة هده algorithme في البسكال