DOC

# java_arithmetic

By Elaine Roberts,2014-10-27 05:45
11 views 0
java_arithmetic

排序的java实现:

Java代码

1.import java.util.*;

2. public class BubbleSort{

3. public void sort(int[] a){ 4. for(int i=0;i

5. for(int j=a.length-1;j>=i+1;j--){ 6. if(a[j]

7. int tmp =a[j];

8. a[j]=a[j-1];

9. a[j-1]=tmp;

10.}

11.}

12.}

13.}

14.public static void main(String[] args){

15.int[] a = {1,6,3,8,1,56,};

16.BubbleSort bs = new BubbleSort();

17.bs.sort(a);

18.System.out.println(Arrays.toString(a));

19.}

20.}

21.

22.2 InsertSort

23.import java.util.*; 24.public class InsertSort{ 25.private int i=0;

26.public void sort(int[] a){ 27.for(int j=1;j

28.int keys = a[j];

29.i =j-1;

30.while(i>=0&&a[i]>keys){

31.a[i+1]=a[i];

32.i--;

33.}

34.a[i+1]=keys;

35.}

36.}

37.public static void main(String[] args){

38.InsertSort i = new InsertSort();

39.int[] f={5,2,4,6,1,3,0};

40.i.sort(f);

41.System.out.println(Arrays.toString(f));

42.}

43.}

44.3 MergeSort

45.import java.util.*; 46.public class MergeSortTest{ 47.private int[] l,r1; 48.public void merge(int[] a,int p,int q,int r){

49.int n1 =q-p+1;

50.int n2 = r-q;

51.l=new int[n1];

52.r1 = new int[n2+1];

53.for(int i=0;i

l[i]=a[p+i]; 54.

55.}

56.l[n1-1]=Integer.MAX_VALUE;

for(int i=0;i 57.

58.r1[i]=a[q+i];

59.}

60.r1[n2] =Integer.MAX_VALUE; 61.int i=0;

62.int j=0;

63.for(int k=p;k

64.if(l[i]<=r1[j]){ 65.a[k]=l[i];

66.i=i+1;

67.}else{

68.a[k]=r1[j];

69.j=j+1;

70.}

71.}

72.}

73.public void mergeSort(int[] a,int p,int r){

74.if(p+1

75.int q=(p+r)/2;

76.mergeSort(a,p,q); 77.mergeSort(a,q,r); 78.merge(a,p,q,r);

79.}

80.}

81.public static void main(String[] args){

82.int[] a1 = {3,41,52,26,38,57,9,49};

83.MergeSortTest mst =new MergeSortTest();

84.mst.mergeSort(a1,0,a1.length); 85.System.out.println(Arrays.toString(a1));

86.}

87.}

88.4 SelectionSort

89.import java.util.*; 90.public class MergeSortTest{ 91.private int[] l,r1; 92.public void merge(int[] a,int p,int q,int r){

93.int n1 =q-p+1;

94.int n2 = r-q;

95.l=new int[n1];

96.r1 = new int[n2+1];

97.for(int i=0;i

l[i]=a[p+i]; 98.

99.}

100. l[n1-1]=Integer.MAX_VALUE;

for(int i=0;i 101.

102. r1[i]=a[q+i];

103. }

104. r1[n2] =Integer.MAX_VALUE; 105. int i=0;

106. int j=0;

107. for(int k=p;k

108. if(l[i]<=r1[j]){

109. a[k]=l[i];

110. i=i+1;

111. }else{

112. a[k]=r1[j];

113. j=j+1;

114. }

115. }

116. }

117. public void mergeSort(int[] a,int p,int r){

118. if(p+1

119. int q=(p+r)/2;

120. mergeSort(a,p,q); 121. mergeSort(a,q,r); 122. merge(a,p,q,r);

123. }

124. }

125. public static void main(String[] args){

126. int[] a1 = {3,41,52,26,38,57,9,49}; 127. MergeSortTest mst =new MergeSortTest();

128. mst.mergeSort(a1,0,a1.length); 129. System.out.println(Arrays.toString(a1));

130. }

131. }

132. 5 HeapSort

133. import java.util.*; 134. public class HeapSort{ 135. private int largest; 136. public int left(int i){ 137. return 2*i+1;

138. }

139. public int right(int j){ 140. return 2*j+2;

141. }

public void maxHeapify(int[] a,int i){ 142.

143. int l=left(i);

144. int r=right(i);

if((la[i])){ 145.

146. largest=l;

147. }else{

148. largest=i;

149. }

150. if((ra[largest])){ 151. largest=r;

152. }

153. if(largest!=i){

154. int temp = a[i];

155. a[i]=a[largest];

156. a[largest]=temp;

157. maxHeapify(a,largest); 158. }

159. }

160. public void buildMaxHeap(int[] a){

161. for(int i=a.length/2;i>=0;--i){ 162. maxHeapify(a,i);

163. }

164. }

165. public void sort(int[] a){ 166. buildMaxHeap(a);

167. //System.out.println(Arrays.toString(a));

168. for(int i=a.length-1;i>=1;--i){

169. int temp=a[0];

170. a[0]=a[i];

171. a[i]=temp;

172. int[] b= new int[i];

173. System.arraycopy(a,0,b,0,i-1);

174. maxHeapify(b,0);

175. System.arraycopy(b,0,a,0,i-1);

176. }

177. }

178. public static void main(String[] args){ 179. HeapSort hs = new HeapSort(); 180. int[] a={23,17,14,6,13,10,1,5,7};

181. hs.sort(a);

182. System.out.println(Arrays.toString(a)); 183. }

184. }

185. 6 BucketSort

import java.util.*; 186.

187. public class BucketSort {

188. /**

* @param args 189.

190. */

192. public void sort(double[] a){ 193. int n=a.length;

194. b=new LinkedList[a.length]; 195. for(int i=0;i

196. b[(int)(n*a[i])] = new LinkedList(); 197. }

198. for(int i=0;i

200. //System.out.println(b[(int)(n*a[i])]); 201. }

202. //System.out.println(Arrays.toString(b)); 203. for(int i=0;i

204. if(b[i]==null){

205. continue;

206. }else{

207. Collections.sort(b[i]);

208. }

209. }

210. }

211. public static void main(String[] args) { 212. // TODO Auto-generated method stub

213. double[] a ={0.79,0.13,0.16,0.64,0.39,0.20,0.89,0.53,0.71,

0.42};

214. BucketSort bs = new BucketSort(); 215. bs.sort(a);

216. for(int i=0;i

217. if(bs.b[i]==null){

218. continue;

219. }else{

220. Iterator it =bs.b[i].iterator(); 221. while(it.hasNext()){

222. System.out.print(it.next()+" "); 223. }

224. }

225. }

226. //System.out.println(Arrays.toString(bs.b));

227. }

228. }

7 CountingSort 229.

230. import java.util.*;

231. public class CountingSort {

/** 232.

233. * @param args

234. */

235. public void Sort(int[] a,int[] b,int k){

236. int[] c= new int[k+1];

237. for(int j=0;j

238. c[a[j]]=c[a[j]]+1;

239. }

240. for(int i=1;i

241. c[i]=c[i]+c[i-1];

242. }

243. for(int j=a.length-1;j>=0;j--){

244. b[c[a[j]]-1]=a[j];

245. c[a[j]]=c[a[j]]-1;

246. }

247. }

248. public static void main(String[] args) {

249. // TODO Auto-generated method stub 250. int[] a=new int[]{3,1,12,11,4,13};

251. CountingSort cs = new CountingSort(); 252. int[] b = new int[a.length]; 253. cs.Sort(a,b,13);

254. System.out.println(Arrays.toString(b)); 255. }

256. }

1 Fibonacci

Fibonacci1200年代的欧洲数学家?在他的著作中曾经提到?若有一只兔子每个月生一只小兔子?一个月后小兔子也开始生产。起初只有一只兔子?一个月后就有两只兔子?两个月后有三只兔子?三个月后有五只兔子?小兔子投入生产?„„

这就是Fibonacci数列?一般习惯称之为费式数列?例如?1?1?2?3?5?8?13?21?34?55?89?„„

Java代码

1. public class Fibonacci {

2. public static void main(String[] args) {

3. int[] fib = new int[20];

4.

5. fib[0] = 0;

6. fib[1] = 1;

7.

8. for(int i = 2; i < fib.length; i++)

fib[i] = fib[i-1] + fib[i-2]; 9.

10.

11. for(int i = 0; i < fib.length; i++)

System.out.print(fib[i] + " "); 12.

13. System.out.println();

14. }

15.}

2 巴斯卡?Pascal?

三角形基本上就是在解nCr ?因为三角形上的每一个数字各对应一个nCr ?其nrow?而rcolnmu

Java代码

1. import java.awt.*;

2. import javax.swing.*;

3.

4. public class Pascal extends JFrame { 5. public Pascal() {

6. setBackground(Color.white); 7. setTitle("巴斯卡三角形");

8. setSize(520, 350);

9. setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

10. show();

11. }

12.

13. private long combi(int n, int r){ 14. int i;

15. long p = 1;

16.

17. for(i = 1; i <= r; i++)

18. p = p * (n-i+1) / i;

19.

20. return p;

} 21.

22.

23. public void paint(Graphics g) {

final int N = 12; 24.

25. int n, r, t;

26.

27. for(n = 0; n <= N; n++) {

28. for(r = 0; r <= n; r++)

29. g.drawString(" " + combi(n, r),

30. (N-n)*20 + r * 40, n * 20 + 50);

31. }

32. }

33.

34. public static void main(String args[]) {

35. Pascal frm = new Pascal(); 36. }

37.}

3 ThreeColorFlags

ThreeColorFlags问题最早由E.W.Dijkstra所提出?塔所使用的用语为Dutch

Nation Flag?Dijkstra为荷兰人??而多数的作者则使用Three-Color Flag

来说明。

假设有一条绳子?上面有红?白?蓝三种颜色的旗子?起初绳子上的旗子颜色并

没有顺序?您希望将之分类?并排列蓝?白?红的顺序?要如何移动次数才会最

少?注意您只能在绳子上进行这个动作?而且一次只能调换两个旗子。

Java代码

1. import java.io.*;

2.

3. public class ThreeColorsFlags {

4. private void swap(char[] flags, int x, int y) { 5. char temp;

6. temp = flags[x];

7. flags[x] = flags[y];

8. flags[y] = temp;

9. }

10.

11. public String move(char[] flags) { 12. int wFlag = 0;

13. int bFlag = 0;

14. int rFlag = flags.length - 1;

15.

16. while(wFlag <= rFlag) {

17. if(flags[wFlag] == 'W') { 18. wFlag++;

19. }

20. else if(flags[wFlag] == 'B') { 21. swap(flags, bFlag, wFlag); 22. bFlag++;

23. wFlag++;

24. }

25. else {

26. while(wFlag < rFlag && flags[rFlag] == 'R')

27. rFlag--;

28. swap(flags, rFlag, wFlag); 29. rFlag--; 30. }

31. }

32.

33. return new String(flags); 34. }

35.

36. public static void main(String[] args) 37. throws IOException {

41.

42. System.out.print("输入三色旗顺序?ex. RWBBWRWR??"); 43. String flags = buf.readLine(); 44.

45. ThreeColorsFlags threeColorsFlag = new ThreeColorsFlags

();

46. flags = threeColorsFlag.move( 47. flags.toUpperCase().toCharArray());

48.

49. System.out.println("移动顺序后?" + flags); 50. }

51.}

4 Mouse

Mouse走迷宫是循环求解的基本类型?我们在二维数组中用2来表示迷宫的墙壁?

使用1来表示老鼠的行走路径?并用程序求出从入口到出口的距离。

Java代码

1. public class Mouse {

2. private int startI, startJ; // 入口

3. private int endI, endJ; // 出口

4. private boolean success = false; 5.

6. public static void main(String[] args) { 7. int[][] maze = {{2, 2, 2, 2, 2, 2, 2},

8. {2, 0, 0, 0, 0, 0, 2},

9. {2, 0, 2, 0, 2, 0, 2},

10. {2, 0, 0, 2, 0, 2, 2},

11. {2, 2, 0, 2, 0, 2, 2},

12. {2, 0, 0, 0, 0, 0, 2},

13. {2, 2, 2, 2, 2, 2, 2}};

14.

15. System.out.println("显示迷宫?");

16. for(int i = 0; i < maze.length; i++) {

Report this document

For any questions or suggestions please email
cust-service@docsford.com