خوارزمية خلطها هي مشكلة عشوائية شائعة نواجهها عند لعب الألعاب والفرز عشوائيًا. يمكن تجريده مثل هذا: احصل على مجموعة ترتيب عشوائية من جميع الأرقام الطبيعية داخل M.
البحث عن "خوارزمية التعديل" على Baidu ، كانت النتيجة الأولى هي "مكتبة Baidu - خوارزمية التعديل". بعد مسح المحتويات ، من السهل تضليل العديد من المحتويات ، بما في ذلك استخدام القوائم المرتبطة لاستبدال المصفوفات في النهاية ، وهو مجرد تحسين محدود (تقدم قوائم الارتباط أيضًا فقدان كفاءة القراءة).
يمكن وصف الطريقة الأولى في هذه المقالة ببساطة على أنها: رسم البطاقات بشكل عشوائي ووضعها في مجموعة أخرى ؛ ارسمها مرة أخرى ، ارسمها مرارًا وتكرارًا عند رسم البطاقات الفارغة.
"ارسم البطاقات بعد رسمها مرة أخرى" سيؤدي إلى فرصة متزايدة لرسم البطاقات لاحقًا ، وهو أمر غير معقول من الواضح.
يمكن تحسين خطوة واحدة: بعد رسم البطاقات ، تصبح البطاقات الأصلية أقل. (بدلاً من ترك البطاقات الفارغة)
الرمز كما يلي:
نسخة الكود كما يلي:
دالة Shuffle_PICK_1 (م) // شوش // طريقة رسم البطاقة
{
// إنشاء بطاقات M.
var arr = new array (m) ؛
لـ (var i = 0 ؛ i <m ؛ i ++) {
arr [i] = i ؛
}
// ارسم بطاقة واحدة في وقت واحد ووضعها في كومة أخرى. نظرًا لأنك تحتاج إلى استخراج عناصر من الصفيف وسحب جميع العناصر اللاحقة إلى الأمام واحدة تلو الأخرى ، فهي تستغرق وقتًا طويلاً.
var arr2 = new array () ؛
لـ (var i = m ؛ i> 0 ؛ i--) {
var rnd = math.floor (math.random ()*i) ؛
arr2.push (arr [rnd]) ؛
arr.splice (rnd ، 1) ؛
}
إرجاع ARR2 ؛
}
من الواضح أن هذا يمثل مشكلة ، لأنه إذا كانت الصفيف كبيرة ، فإن حذف عنصر معين في الوسط سيؤدي إلى اتخاذ قائمة الانتظار إلى الأمام ، وهو إجراء يستغرق وقتًا طويلاً.
أذكر الغرض من "لماذا نحذف هذا العنصر؟" هو تجنب البطاقات الفارغة.
بالإضافة إلى حذف هذا العنصر ، هل لدينا طرق أخرى لإزالة البطاقات الفارغة؟
---- نعم ، نحتاج فقط إلى وضع آخر بطاقة غير مرسومة في وضع السحب.
لذلك ، يمكننا تحسين هذه الفكرة على النحو التالي:
نسخة الكود كما يلي:
وظيفة Shuffle_Pick (M) // طريقة رسم البطاقة //
{
// إنشاء بطاقات M.
var arr = new array (m) ؛
لـ (var i = 0 ؛ i <m ؛ i ++) {
arr [i] = i ؛
}
// ارسم بطاقة واحدة في وقت واحد ووضعها في كومة أخرى. ضع آخر بطاقة Undrensed على المقعد المفتوح.
var arr2 = new array () ؛
لـ (var i = m ؛ i> 0 ؛) {
var rnd = math.floor (math.random ()*i) ؛
arr2.push (arr [rnd]) ؛
arr [rnd] = arr [-i] ؛
}
إرجاع ARR2 ؛
}
بالإضافة إلى فكرة رسم البطاقات ، يمكننا أيضًا استخدام فكرة تغيير البطاقات.
"يذكر Baidu Wenku-shut خوارزمية" فكرة تغيير البطاقة: "قم بتبديل موقعين بشكل عشوائي ، وتبادلها في إجمالي. كلما زاد عدد n ، كلما اقتربوا عشوائيًا."
هذا النهج خاطئ. حتى لو كانت N كبيرة جدًا (على سبيل المثال ، 10 بطاقات ، 10 مفاتيح) ، لا يزال هناك احتمال كبير أن "بعض البطاقات لا تغير المواقف على الإطلاق".
اتبع هذه الفكرة وقم بإجراء القليل من التعديل: قم بتغيير البطاقة I-Th مع أي بطاقة ، وقم بتغييرها لجولة واحدة.
الرمز كما يلي:
نسخة الكود كما يلي:
وظيفة Shuffle_swap (M) // Shush // طريقة تغيير البطاقة
{
// إنشاء بطاقات M.
var arr = new array (m) ؛
لـ (var i = 0 ؛ i <m ؛ i ++) {
arr [i] = i ؛
}
// يتم استخدام بطاقة I-Th لتغيير المقاعد ويمكنك تغييرها لجولة واحدة
لـ (var i = 0 ؛ i <m ؛ i ++) {
var rnd = math.floor (math.random ()*(i+1)) ،
temp = arr [rnd] ؛
arr [rnd] = arr [i] ؛
arr [i] = temp ؛
}
إرجاع arr ؛
}
بالإضافة إلى فكرة رسم البطاقات وتغييرها ، يمكننا أيضًا استخدام فكرة إدراج البطاقات: أولاً هناك بطاقة واحدة ، والبطاقة الثانية لها وضعين يتم إدراجهما بشكل عشوائي (قبل أو خلف البطاقة الأولى)
الرمز كما يلي:
نسخة الكود كما يلي:
دالة Shuffle_Insert_1 (M) // طريقة إدراج بطاقة // بطاقة
{
// في كل مرة ، يتم إنشاء أكبر بطاقة وإدراجها أمام بطاقة عشوائية. نظرًا لأنك تحتاج إلى إدراج عناصر في الصفيف والضغط على جميع العناصر اللاحقة مرة واحدة تلو الأخرى ، فهي تستغرق وقتًا طويلاً.
var arr = [0] ؛
لـ (var i = 1 ؛ i <m ؛ i ++) {
Arr.Splice (Math.Floor (Math.Random ()*(i+1)) ، 0 ، i) ؛
}
إرجاع arr ؛
}
سيواجه الرمز أعلاه أيضًا بعض المشكلات: مع زيادة عدد البطاقات ، يصبح من الصعب إدخال البطاقات ، لأن إدخال البطاقات سيؤدي إلى العديد من البطاقات التي تتبع خطوة واحدة.
بالطبع ، يمكننا أيضًا التحسين بشكل مناسب: أولاً هناك بطاقة N-1 ، يتم وضع بطاقة N-Th في النهاية ، ثم تبادل المواقف مع أي بطاقة.
الرمز كما يلي:
نسخة الكود كما يلي:
وظيفة Shuffle_Insert (M) // shush // يمكن إثبات الإصدار الأمثل من طريقة إدراج البطاقة من خلال الحث الرياضي على أن هذا التجول موحد.
{
// في كل مرة يقوم بإنشاء أكبر بطاقة وتبادل مع بطاقة عشوائية
var arr = new array (m) ؛
arr [0] = 0 ؛
لـ (var i = 1 ؛ i <m ؛ i ++) {
var rnd = math.floor (math.random ()*(i+1)) ؛
arr [i] = arr [rnd] ؛
arr [rnd] = i ؛
}
إرجاع arr ؛
}
حسنًا ، جميع الرموز هي كما يلي. يمكن للطلاب المهتمين تجربتهم على جهازهم الخاص لمعرفة ما إذا كانت كفاءة التنفيذ الخاصة بهم وما إذا كانت النتيجة النهائية عشوائية من الناحية النظرية.
نسخة الكود كما يلي:
<html>
<head>
<meta http-equiv = "content-type" content = "text/html ؛ charset = gb2312">
<title> jk: خوارزمية خلط JavaScript </title>
</head>
<body>
<script type = "text/javaScript">
دالة Shuffle_PICK_1 (م) // شوش // طريقة رسم البطاقة
{
// إنشاء بطاقات M.
var arr = new array (m) ؛
لـ (var i = 0 ؛ i <m ؛ i ++) {
arr [i] = i ؛
}
// ارسم بطاقة واحدة في وقت واحد ووضعها في كومة أخرى. نظرًا لأنك تحتاج إلى استخراج عناصر من الصفيف وسحب جميع العناصر اللاحقة إلى الأمام واحدة تلو الأخرى ، فهي تستغرق وقتًا طويلاً.
var arr2 = new array () ؛
لـ (var i = m ؛ i> 0 ؛ i--) {
var rnd = math.floor (math.random ()*i) ؛
arr2.push (arr [rnd]) ؛
arr.splice (rnd ، 1) ؛
}
إرجاع ARR2 ؛
}
وظيفة Shuffle_Pick (M) // طريقة رسم البطاقة //
{
// إنشاء بطاقات M.
var arr = new array (m) ؛
لـ (var i = 0 ؛ i <m ؛ i ++) {
arr [i] = i ؛
}
// ارسم بطاقة واحدة في وقت واحد ووضعها في كومة أخرى. ضع آخر بطاقة Undrensed على المقعد المفتوح.
var arr2 = new array () ؛
لـ (var i = m ؛ i> 0 ؛) {
var rnd = math.floor (math.random ()*i) ؛
arr2.push (arr [rnd]) ؛
arr [rnd] = arr [-i] ؛
}
إرجاع ARR2 ؛
}
وظيفة Shuffle_swap (M) // Shush // طريقة تغيير البطاقة
{
// إنشاء بطاقات M.
var arr = new array (m) ؛
لـ (var i = 0 ؛ i <m ؛ i ++) {
arr [i] = i ؛
}
// يتم استخدام بطاقة I-Th لتغيير المقاعد ويمكنك تغييرها لجولة واحدة
لـ (var i = 0 ؛ i <m ؛ i ++) {
var rnd = math.floor (math.random ()*(i+1)) ،
temp = arr [rnd] ؛
arr [rnd] = arr [i] ؛
arr [i] = temp ؛
}
إرجاع arr ؛
}
دالة Shuffle_Insert_1 (M) // طريقة إدراج بطاقة // بطاقة
{
// في كل مرة ، يتم إنشاء أكبر بطاقة وإدراجها أمام بطاقة عشوائية. نظرًا لأنك تحتاج إلى إدراج عناصر في الصفيف والضغط على جميع العناصر اللاحقة مرة واحدة تلو الأخرى ، فهي تستغرق وقتًا طويلاً.
var arr = [0] ؛
لـ (var i = 1 ؛ i <m ؛ i ++) {
Arr.Splice (Math.Floor (Math.Random ()*(i+1)) ، 0 ، i) ؛
}
إرجاع arr ؛
}
وظيفة Shuffle_Insert (M) // shush // يمكن إثبات الإصدار الأمثل من طريقة إدراج البطاقة من خلال الحث الرياضي على أن هذا التجول موحد.
{
// في كل مرة يقوم بإنشاء أكبر بطاقة وتبادل مع بطاقة عشوائية
var arr = new array (m) ؛
arr [0] = 0 ؛
لـ (var i = 1 ؛ i <m ؛ i ++) {
var rnd = math.floor (math.random ()*(i+1)) ؛
arr [i] = arr [rnd] ؛
arr [rnd] = i ؛
}
إرجاع arr ؛
}
// ALERT (Shuffle_PICK (10))
var funcs = [Shuffle_pick_1 ، Shuffle_Pick ، Shuffle_swap ، Shuffle_Insert_1 ، Shuffle_Insert] ،
funcnames = ["" Draw Card "،" Draw Card Optimization "،" Card Change "،" Card Insert "،" Card Insert Optimization "]
م = 10000 ،
مرات = [] ؛
لـ (var i = 0 ؛ i <funcs.length ؛ i ++) {
var d0 = date new () ؛
funcs [i] (m) ؛
funcnames [i] = (date date () - d0) + '/t' + funcnames [i] ؛
}
ALERT (funcnames.join ('/n')) ؛
</script>
</body>
</html>