DOC

java_arithmetic

By Elaine Roberts,2014-10-27 05:45
7 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. */

    191. private LinkedList[] b;

    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

    199. b[(int)(n*a[i])].add(Double.valueOf(a[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 {

38. BufferedReader buf;

    39. buf = new BufferedReader( 40. new InputStreamReader(System.in));

    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