1. คำจำกัดความปัญหา:
ถามอาร์เรย์ จุดตัด
ตัวอย่างเช่น:
คัดลอกรหัสรหัสดังนี้:
น้ำหนัก: 8 2 11 79
ค่าที่ส่งคืนด้วยน้ำหนัก: 0 1 2 3
2. การวิเคราะห์ปัญหา:
แนวคิด 1: สร้างอาร์เรย์ของขนาดและน้ำหนักของขนาดและน้ำหนัก หมวดหมู่จะถูกผลักตามลำดับ
จากนั้นใช้จำนวนน้ำหนักและขนาดแบบสุ่มเพื่อสร้างตัวเลขสุ่ม ข้อเสียควรครอบครองหน่วยความจำมากเกินไป
แนวคิด 2:
น้ำหนักและอาร์เรย์ w [i] เก็บน้ำหนักและเวลาที่ซับซ้อนขององค์ประกอบทั้งหมดของ [0, i]
สุ่ม [0, W [399]] ดูว่าเวลาใดที่จำนวนสุ่มลดลงในความซับซ้อนของเวลา o (longn)
ดังนั้นความซับซ้อนของความซับซ้อนของเวลาทั้งหมด o (n) ความซับซ้อนเชิงพื้นที่ o (n)
Pseudocode:
การพนันแบบหมุนไม่ใช่ตัวเลือกที่ดีโดยเฉพาะ แต่เป็นเรื่องง่ายที่จะบรรลุ
ก่อนอื่นจำเป็นต้องเข้าใจว่าเนื่องจากการข้าม -และผู้ประกอบการและผู้ประกอบการอื่น ๆ ทิศทางของวิวัฒนาการไม่สามารถควบคุมได้ดังนั้นความรับผิดชอบอย่างหนักของวิวัฒนาการจึงอยู่ในผู้ดำเนินการคัดเลือก
หากคุณเข้าใจสิ่งนี้มันเป็นเรื่องง่ายที่จะทำ
การพนันแบบหมุนจะสะสมความน่าจะเป็นที่จะบรรลุผล
ถ้า: FIT คือการปรับตัวของอาร์เรย์รหัสคัดลอก M ทั้งหมดมีดังนี้:
สำหรับ i = 1 ถึง m '
sum = sum+fit (i)
ต่อไปฉัน
สำหรับ i = 1 ถึง n 'n- คุณต้องการสร้างบุคคลกี่คน?
temp = temp + fit (i)
ถ้า rnd <= temp / s
เอาต์พุตฉันเป็นผลลัพธ์
ฟังก์ชั่นออก
สิ้นสุดถ้า
ต่อไปฉัน
ประการที่สามแก้ปัญหา:
คัดลอกรหัสรหัสดังนี้:
แพ็คเกจข้อมูล
นำเข้า java.util.hashmap;
นำเข้า java.util.map;
-
หมายเลขสุ่มน้ำหนัก:
ถ้าน้ำหนัก: 8 2 11 79
ค่าที่ส่งคืนด้วยน้ำหนัก: 0 1 2 3
@author Ajian005 79331356@qq.com
2014-2-16 21:12
ผลลัพธ์ผลลัพธ์: {2.0 = 184128, 11.0 = 348551, 79.0 = 1308100, 8.0 = 159221}}
-
ระดับสาธารณะ WeightTrandomTest {
เอกชนคงที่ [] weightarrays = {8.0, 2.0, 11.0,79.0};
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {{
WeighTrandom WeightTrandom = new WeighTrandom ();
แผนที่ <สองครั้ง, จำนวนเต็ม> stat = new hashmap <double, integer> ();
สำหรับ (int i = 0; i <2000000; i ++) {
int weightValue = WeighTrandom.getWeighTrandom (WeightArrays);
if (weightValue <0) {{
ดำเนินการต่อ;
-
System.out.println ("หมายเลขสุ่มส่งคืนโดยน้ำหนัก:" + weightValue);
if (stat.get (weightarrays [weightValue]) == null) {
stat.put (weightarrays [weightValue], 1);
} อื่น {
stat.put (weightarrays [weightValue], stat.get (weightarrays [weightValue])+1);
-
-
System.out.println (Stat);
-
-
คลาสชั่งน้ำหนัก {
java.util.random r = ใหม่ java.util.random ();
private double weightarraysum (double [] weightarrays) {{
double weightsum = 0;
สำหรับ (Double WeightValue: WeightArrays) {
Weightsum += WeightValue;
-
คืนน้ำหนัก;
-
สาธารณะ int getWeighTrandom (double [] weightArrays) {{
double weightsum = weightarraysum (weightarrays);
สอง stepweightsum = 0;
สำหรับ (int i = 0; i <weightarrays.length; i ++) {
stepweightsum += weightarrays [i];
if (math.random () <= stepweightsum/weightsum) {
//system.out.println (i);
กลับฉัน;
-
-
System.out.println ("ข้อผิดพลาด");
กลับ -1;
-
-
ประการที่สี่สรุปสรุป:
การพนันรอบรัสเซียคือการสะสมความน่าจะเป็นที่จะบรรลุเป้าหมาย
การกำหนดเวลาโหลดขึ้นอยู่กับ ฯลฯ