برنامه ای بنویسید که n عدد تصادفی غیر تکراری را با ساختمان داده آرایه پیاده سازی نماید.

Question

برنامه ای بنویسید که n عدد تصادفی غیر تکراری را با ساختمان داده آرایه پیاده سازی نماید.

سوال

در حال بررسی 0

انجمن برنامه نویسان جاوا rose 2 سال 1 پاسخ 172 دیده شده 0

درباره rose

پاسخ ( ۱ )

ارسال یک پاسخ

سوال قبلی

سوال بعدی

mort · Answer 1 · ۱۴۰۱-۱۱-۰۳

الگوریتم تقسیم‌بندی ناحیه‌ی انتخاب:

۱- ابتدا یک عدد در یک بازه انتخاب می‌شود مانند ۶۰ در بازه ۱۰۰ تا -۱۰۰

۲- سپس دو بازه خالی بوجود می‌آید: -۱۰۰ تا ۵۹ و ۶۱ تا ۱۰۰٫ حال دوباره یکی از این بازه‌ها به‌صورت رندومی انتخاب می‌شود و در این بازه یک عدد به‌صورت رندومی انتخاب می‌شود به‌طور مثال -۱۰ در بازه -۱۰۰ تا ۵۹٫

۳- سپس بازه های خالی دوباره محاسبه می شوند و در یکی از بازه های خالی یک عدد به صورت رندومی انتخاب می شود.

این روند تا زمانی ادامه دارد که n عدد رندوم انتخاب شوند.

برای تعیین بازه‌ی Universal باید MAX_VAL و MIN_VAL در کدها تنظیم کنید. مقدار اولیه اونها ۱۰۰۰ و -۱۰۰۰ هست. این یعنی شما نهایتاً ۲۰۰۱ عدد رندوم غیرتکراری می‌توانید تولید کنید.

سرعت این الگوریتم در بازه های بزرگ (به‌طور مثال تولید ۱ میلیون عدد تصادفی غیرتکراری) بیشتر از الگوریتم‌های دیگر است.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

public class Main {
	public static void main(String[] args) {
		int n = 1000;
		int[] rands = new int[n];
		ArrayList<IntRange> emptyRanges = new ArrayList<>();
		ArrayList<IntRange> ladenRanges = new ArrayList<>();
		emptyRanges.add(IntRange.getRange(MIN_VAL, MAX_VAL + 1));
		Comparator<IntRange> comparator = new Comparator<Test2.IntRange>() {
			@Override
			public int compare(Test2.IntRange o1, Test2.IntRange o2) {
				if (o1.start > o2.start) {
					return 1;
				} else if (o1.start < o2.start) {
					return -1;
				} else {
					return 0;
				}
			}
		};

		int rand;

		boolean expanded;

		Long startTime = System.nanoTime();

		for (int j = 0; j < n; j++) {
			rand = getRandomIntFrom(emptyRanges.get(random.nextInt(0, emptyRanges.size())));
			expanded = false;
			for (int i = 0; i < ladenRanges.size(); i++) {
				if (isNextOf(rand, ladenRanges.get(i))) {
					expandForward(rand, ladenRanges.get(i));
					if (i < ladenRanges.size() - 1) {
						if (isPreviusOf(ladenRanges.get(i), ladenRanges.get(i + 1))) {
							expandForward(ladenRanges.get(i + 1).end, ladenRanges.get(i));
							ladenRanges.remove(i + 1);
						}
					}
					expanded = true;
				} else if (isPreviusOf(rand, ladenRanges.get(i))) {
					expandBackward(rand, ladenRanges.get(i));
					if (i > 0) {
						if (isNextOf(ladenRanges.get(i), ladenRanges.get(i - 1))) {
							expandBackward(ladenRanges.get(i - 1).start, ladenRanges.get(i));
							ladenRanges.remove(i - 1);
						}
					}
					expanded = true;
				}
				if (expanded)
					break;
			}
			if (!expanded) {
				ladenRanges.add(IntRange.getRange(rand));
				Collections.sort(ladenRanges, comparator);
			}
			rands[j] = rand;
			setEmptySpacesTo(emptyRanges, ladenRanges);
		}
		System.out.println("Result ===>");
		System.out.println(Arrays.toString(rands));
		System.out.println("The array was create in " + ((System.nanoTime() - startTime) / 1_000_000_000.0) + " sec.");
	}

	public static class IntRange {
		public IntRange(int start, int end) {
			this.start = start;
			this.end = end;
		}
		public IntRange(int start) {
			this(start, start);
		}
		public static IntRange getRange(int start, int end) {
			return new IntRange(start, end);
		}
		public static IntRange getRange(int start) {
			return new IntRange(start);
		}
		public double getDistance() {
			return Math.abs(end - start);
		}
		@Override
		public String toString() {
			return String.format("[%s, %s]", start, end);
		}
		int start, end;
	}

	public static boolean isNextOf(int integer, IntRange range) {
		return range.end + 1 == integer;
	}

	public static boolean isNextOf(IntRange range1, IntRange range2) {
		return range1.start - 1 == range2.end;
	}

	public static boolean isPreviusOf(int integer, IntRange range) {
		return range.start - 1 == integer;
	}

	public static boolean isPreviusOf(IntRange range1, IntRange range2) {
		return range1.end + 1 == range2.start;
	}

	public static void expandForward(int newEnd, IntRange range) {
		range.end = newEnd;
	}

	public static void expandBackward(int newStart, IntRange range) {
		range.start = newStart;
	}

	public static int getRandomIntFrom(IntRange range) {
		return random.nextInt(range.start, range.end);
	}

	public static void setEmptySpacesTo(ArrayList<IntRange> empty, ArrayList<IntRange> laden) {
		empty.clear();
		if (laden.get(0).start > MIN_VAL) {
			empty.add(IntRange.getRange(MIN_VAL, laden.get(0).start));
		}
		for (int i = 0; i < laden.size() - 1; i++) {
			empty.add(IntRange.getRange(laden.get(i).end + 1, laden.get(i + 1).start));
		}
		if (laden.get(laden.size() - 1).end < MAX_VAL) {
			empty.add(IntRange.getRange(laden.get(laden.size() - 1).end + 1, MAX_VAL + 1));
		}
	}

	static Random random = new Random();
	public final static int MAX_VAL = 1000;
	public final static int MIN_VAL = -1000;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.Comparator;

import java.util.Random;

public class Main {

public static void main(String[] args) {

int n = 1000;

int[] rands = new int[n];

ArrayList<IntRange> emptyRanges = new ArrayList<>();

ArrayList<IntRange> ladenRanges = new ArrayList<>();

emptyRanges.add(IntRange.getRange(MIN_VAL, MAX_VAL + 1));

Comparator<IntRange> comparator = new Comparator<Test2.IntRange>() {

@Override

public int compare(Test2.IntRange o1, Test2.IntRange o2) {

if (o1.start > o2.start) {

return 1;

} else if (o1.start < o2.start) {

return -1;

} else {

return 0;

}

};

int rand;

boolean expanded;

Long startTime = System.nanoTime();

for (int j = 0; j < n; j++) {

rand = getRandomIntFrom(emptyRanges.get(random.nextInt(0, emptyRanges.size())));

expanded = false;

for (int i = 0; i < ladenRanges.size(); i++) {

if (isNextOf(rand, ladenRanges.get(i))) {

expandForward(rand, ladenRanges.get(i));

if (i < ladenRanges.size() - 1) {

if (isPreviusOf(ladenRanges.get(i), ladenRanges.get(i + 1))) {

expandForward(ladenRanges.get(i + 1).end, ladenRanges.get(i));

ladenRanges.remove(i + 1);

}

expanded = true;

} else if (isPreviusOf(rand, ladenRanges.get(i))) {

expandBackward(rand, ladenRanges.get(i));

if (i > 0) {

if (isNextOf(ladenRanges.get(i), ladenRanges.get(i - 1))) {

expandBackward(ladenRanges.get(i - 1).start, ladenRanges.get(i));

ladenRanges.remove(i - 1);

}

expanded = true;

}

if (expanded)

break;

}

if (!expanded) {

ladenRanges.add(IntRange.getRange(rand));

Collections.sort(ladenRanges, comparator);

}

rands[j] = rand;

setEmptySpacesTo(emptyRanges, ladenRanges);

}

System.out.println("Result ===>");

System.out.println(Arrays.toString(rands));

System.out.println("The array was create in " + ((System.nanoTime() - startTime) / 1_000_000_000.0) + " sec.");

}

public static class IntRange {

public IntRange(int start, int end) {

this.start = start;

this.end = end;

}

public IntRange(int start) {

this(start, start);

}

public static IntRange getRange(int start, int end) {

return new IntRange(start, end);

}

public static IntRange getRange(int start) {

return new IntRange(start);

}

public double getDistance() {

return Math.abs(end - start);

}

@Override

public String toString() {

return String.format("[%s, %s]", start, end);

}

int start, end;

}

public static boolean isNextOf(int integer, IntRange range) {

return range.end + 1 == integer;

}

public static boolean isNextOf(IntRange range1, IntRange range2) {

return range1.start - 1 == range2.end;

}

public static boolean isPreviusOf(int integer, IntRange range) {

return range.start - 1 == integer;

}

public static boolean isPreviusOf(IntRange range1, IntRange range2) {

return range1.end + 1 == range2.start;

}

public static void expandForward(int newEnd, IntRange range) {

range.end = newEnd;

}

public static void expandBackward(int newStart, IntRange range) {

range.start = newStart;

}

public static int getRandomIntFrom(IntRange range) {

return random.nextInt(range.start, range.end);

}

public static void setEmptySpacesTo(ArrayList<IntRange> empty, ArrayList<IntRange> laden) {

empty.clear();

if (laden.get(0).start > MIN_VAL) {

empty.add(IntRange.getRange(MIN_VAL, laden.get(0).start));

}

for (int i = 0; i < laden.size() - 1; i++) {

empty.add(IntRange.getRange(laden.get(i).end + 1, laden.get(i + 1).start));

}

if (laden.get(laden.size() - 1).end < MAX_VAL) {

empty.add(IntRange.getRange(laden.get(laden.size() - 1).end + 1, MAX_VAL + 1));

}

static Random random = new Random();

public final static int MAX_VAL = 1000;

public final static int MIN_VAL = -1000;

}