Brian Warehouse

You are given natural numbers a and b. Find a^b-b^a.

Input contains numbers a and b (1≤a,b≤100).

Write answer to output.

Sample Input

2 3

Sample Output

-1

一看到這種題目，就想到高精度算法，Java的大數。
此舉確實流氓了一點，不過確實過了，鄙人的第一題SGU啊，不許打擊。
過段時間看看能不能寫出 (C++ Edition) ,啥也別說了，上代碼。

import java.math.*;
import java.util.*;

public class Solution
{
   public static void main(String[] args)
   {
      Scanner in = new Scanner(System.in);
      int a = in.nextInt();
      int b = in.nextInt();
      
      BigInteger A=BigInteger.valueOf(a);
      BigInteger B=BigInteger.valueOf(b); // A^B
      BigInteger rA=BigInteger.valueOf(a);
      BigInteger rB=BigInteger.valueOf(b); // store the result after computing
      
      for(int i=1; i<b; i++) // just b-1 times
          rA=rA.multiply(A);
      for(int i=1; i<a; i++)    
          rB=rB.multiply(B);
      System.out.println(rA.subtract(rB)); // sub
   }
}

附《Core Java I》里關于 大數的簡單介紹，講的算比較清晰的了：
Big Numbers
If the precision of the basic integer and floating-point types is not sufficient, you can
turn to a couple of handy classes in the java.math package: BigInteger and BigDecimal. These
are classes for manipulating numbers with an arbitrarily long sequence of digits. The
BigInteger class implements arbitrary precision integer arithmetic, and BigDecimal does the
same for floating-point numbers.
Use the static valueOf method to turn an ordinary number into a big number:
BigInteger a = BigInteger.valueOf(100);
Unfortunately, you cannot use the familiar mathematical operators such as + and * to
combine big numbers. Instead, you must use methods such as add and multiply in the big
number classes.
BigInteger c = a.add(b); // c = a + b
BigInteger d = c.multiply(b.add(BigInteger.valueOf(2))); // d = c * (b + 2)
C++ NOTE: Unlike C++, Java has no programmable operator overloading. There was no way
for the programmer of the BigInteger class to redefine the + and * operators to give the add and
multiply operations of the BigInteger classes. The language designers did overload the + operator
to denote concatenation of strings. They chose not to overload other operators, and they
did not give Java programmers the opportunity to overload operators in their own classes.
Listing 3–6 shows a modification of the lottery odds program of Listing 3–5, updated to
work with big numbers. For example, if you are invited to participate in a lottery in
which you need to pick 60 numbers out of a possible 490 numbers, then this program
will tell you that your odds are 1 in 7163958434619955574151162225400929334117176
12789263493493351 013459481104668848. Good luck!
The program in Listing 3–5 computed the statement
lotteryOdds = lotteryOdds * (n - i + 1) / i;
When big numbers are used, the equivalent statement becomes
lotteryOdds = lotteryOdds.multiply(BigInteger.valueOf(n - i + 1)).divide(BigInteger.valueOf(i));
Listing 3–6 BigIntegerTest.java
1. import java.math.*;
2. import java.util.*;
3.
4. /**
5. * This program uses big numbers to compute the odds of winning the grand prize in a lottery.
6. * @version 1.20 2004-02-10
7. * @author Cay Horstmann
8. */
9. public class BigIntegerTest
10. {
11. public static void main(String[] args)
12. {
13. Scanner in = new Scanner(System.in);
14.
15. System.out.print("How many numbers do you need to draw? ");
16. int k = in.nextInt();
17.
18. System.out.print("What is the highest number you can draw? ");
19. int n = in.nextInt();
20.
21. /*
22. * compute binomial coefficient n*(n-1)*(n-2)*...*(n-k+1)/(1*2*3*...*k)
23. */
24.
25. BigInteger lotteryOdds = BigInteger.valueOf(1);
26.
27. for (int i = 1; i <= k; i++)
28. lotteryOdds = lotteryOdds.multiply(BigInteger.valueOf(n - i + 1)).divide(
29. BigInteger.valueOf(i));
30.
31. System.out.println("Your odds are 1 in " + lotteryOdds + ". Good luck!");
32. }
33. }

java.math.BigInteger

? BigInteger add(BigInteger other)
? BigInteger subtract(BigInteger other)
? BigInteger multiply(BigInteger other)
? BigInteger divide(BigInteger other)
? BigInteger mod(BigInteger other)
returns the sum, difference, product, quotient, and remainder of this big integer and
other.
? int compareTo(BigInteger other)
returns 0 if this big integer equals other, a negative result if this big integer is less
than other, and a positive result otherwise.
? static BigInteger valueOf(long x)
returns a big integer whose value equals x.
? BigDecimal add(BigDecimal other)
? BigDecimal subtract(BigDecimal other)
? BigDecimal multiply(BigDecimal other)
? BigDecimal divide(BigDecimal other, RoundingMode mode) 5.0
returns the sum, difference, product, or quotient of this big decimal and other.
To compute the quotient, you must supply a rounding mode. The mode
RoundingMode.HALF_UP is the rounding mode that you learned in school (i.e., round
down digits 0 . . . 4, round up digits 5 . . . 9). It is appropriate for routine
calculations. See the API documentation for other rounding modes.
? int compareTo(BigDecimal other)
returns 0 if this big decimal equals other, a negative result if this big decimal is less
than other, and a positive result otherwise.
? static BigDecimal valueOf(long x)
? static BigDecimal valueOf(long x, int scale)
returns a big decimal whose value equals x or x /10scale.

一、實驗內容

利用高級語言，設計一個采用二級或二級以上的多級文件目錄管理系統，實現對文件的基本操作，如：文件的建立、打開、關閉、復制、撤銷、檢索等。

二、實驗目的

用高級語言編寫和調試一個簡單的文件系統，模擬文件管理的工作過程。從而對各種文件操作命令的實質內容和執行過程有比較深入的了解。

要求設計一個 n個用戶的文件系統，每次用戶可保存m個文件，用戶在一次運行中只能打開一個文件，對

文件必須設置保護措施，且至少有Create、delete、open、close、read、write等命令。

三、實驗環境

1．PC微機。

2．Windows 操作系統。

3．C/C++/VB開發集成環境。

四、實驗題目

設計一個10個用戶的文件系統，每次用戶可保存10個文件，一次運行用戶可以打開5個文件。 程序采用二級文件目錄（即設置主目錄[MFD]）和用戶文件目錄（UED）。另外，為打開文件設置了運行文件目錄（AFD）。 為了便于實現，對文件的讀寫作了簡化，在執行讀寫命令時，只需改讀寫指針，并不進行實際的讀寫操作。

算法設計思想：

（1）       因系統小，文件目錄的檢索使用了簡單的線性搜索。

（2）       文件保護簡單使用了三位保護碼：允許讀寫執行、對應位為 1，對應位為0，則表示不允許讀寫、執行。

（3）       程序中使用的主要設計結構如下：

主文件目錄和用戶文件目錄（ MFD、UFD），  打開文件目錄（ AFD）（即運行文件目錄）

一、實驗內容

利用高級語言模擬進程的時間片輪轉調度算法，響應比高者優先調度算法。

二、實驗目的

在采用多道程序設計的系統中，往往有若干個進程同時處于就緒狀態。當就緒進程個數大于處理器數時，就必須依照某種策略來決定哪些進程優先占用處理器。本實驗模擬在單處理器情況下的處理器調度，幫助學生加深了解處理器調度的工作。

三、實驗環境

1．PC微機。

2．Windows 操作系統。

3．C/C++/VB開發集成環境。

四、實驗題目

本實驗有兩個小題。

第一題：設計一個按時間片輪轉法實現處理器調度的程序。

算法設計思想：

(1) 假定系統有五個進程，每一個進程用一個進程控制塊PCB來代表。進程控制塊的格式為：

其中，進程名——作為進程的標識，假設五個進程的進程名分別為Q₁，Q₂，Q₃，Q₄，Q₅。

指針——進程按順序排成循環隊列，用指針指出下一個進程的進程控制塊的首地址，最后一個進程的指針指出第一個進程的進程控制塊首地址。

要求運行時間——假設進程需要運行的單位時間數。

已運行時間——假設進程已經運行的單位時間數，初始值為“0”。

狀態——有兩種狀態，“就緒”和“結束”，初始狀態都為“就緒”，用“R”表示。當一個進程運行結束后，它的狀態為“結束”，用“E”表示。

(2) 每次運行所設計的進程調度程序前，為每個進程任意確定它的“要求運行時間”。

(3) 把五個進程按順序排成循環隊列，用指針指出隊列連接情況。另用一標志單元記錄輪到運行的進程。例如，當前輪到P₂執行，則有：

標志單元

         K₂   

(4) 處理器調度總是選擇標志單元指示的進程運行。由于本實驗是模擬處理器調度的功能，所以，對被選中的進程并不實際的啟動運行，而是執行：

已運行時間+1

來模擬進程的一次運行，表示進程已經運行過一個單位的時間。

請注意：在實際的系統中，當一個進程被選中運行時，必須置上該進程可以運行的時間片值，以及恢復進程的現場，讓它占有處理器運行，直到出現等待事件或運行滿一個時間片。在這時省去了這些工作，僅用“已運行時間+1”來表示進程已經運行滿一個時間片。

(5) 進程運行一次后，應把該進程的進程控制塊中的指針值送到標志單元，以指示下一個輪到運行的進程。同時，應判斷該進程的要求運行時間與已運行時間，若該進程的要求運行時間?已運行時間，則表示它尚未執行結束，應待到下一輪時再運行。若該進程的要求運行時間=已運行時間，則表示它已經執行結束，應指導它的狀態修改成“結束”（E）且退出隊列。此時，應把該進程的進程控制塊中的指針值送到前面一個進程的指針位置。

(6) 若“就緒”狀態的進程隊列不為空，則重復上面的（4）和（5）的步驟，直到所有的進程都成為“結束”狀態。

(7) 在所設計的程序中應有顯示或打印語句，能顯示或打印每次選中進程的進程名以及運行一次后進程隊列的變化。

(8) 為五個進程任意確定一組“要求運行時間”，啟動所設計的處理器調度程序，顯示或打印逐次被選中的進程名以及進程控制塊的動態變化過程。

第二題：設計一個按響應比高者優先調度算法實現進程調度的程序。

算法設計思想：

 (1) 假定系統有五個進程，每一個進程用一個進程控制塊PCB來代表，進程控制塊的格式為：

其中，進程名——作為進程的標識，假設五個進程的進程名分別為P₁，P₂，P₃，P₄，P₅。

指針——按優先數的大小把五個進程連成隊列，用指針指出下一個進程的進程控制塊的首地址，最后一個進程中的指針為“0”。

要求運行時間——假設進程需要運行的單位時間數。

等待時間——自最近一次調度運行至今等待的時間數，當進程被調度時等待時間清零。

響應比——進程調度程序運行前計算每個進程的響應比，調度時總是選取響應比大的進程先執行，每次執行一個固定的時間片。

狀態——可假設有兩種狀態，“就緒”狀態和“結束”狀態。五個進程的初始狀態都為“就緒”，用“R”表示，當一個進程運行結束后，它的狀態為“結束”，用“E”表示。

(2) 在每次運行你所設計的處理器調度程序之前，為每個進程任意確定它的“等待時間”和“要求運行時間”。

(3) 為了調度方便，把五個進程按給定的響應比從大到小連成隊列。用一單元指出隊首進程，用指針指出隊列的連接情況。例：

  隊首標志

         K₂   

(4) 處理器調度總是選隊首進程運行。采用動態改變響應比的辦法，進程每運行一次重新計算各進程的響應比。由于本實驗是模擬處理器調度，所以，對被選中的進程并不實際的啟動運行，而是執行：要求運行時間-1、等待時間為0。其它進程等待時間+1，重新計算各進程的響應比，并從大到小排序。

提醒注意的是：在實際的系統中，當一個進程被選中運行時，必須恢復進程的現場，讓它占有處理器運行，直到出現等待事件或運行結束。在這里省去了這些工作。

(5) 進程運行一次后，若要求運行時間?0，則再將它加入隊尾（因其響應比最小。）；若要求運行時間=0，則把它的狀態修改成“結束”（E），且退出隊列。

(6) 若“就緒”狀態的進程隊列不為空，則重復上面（4）和（5）的步驟，直到所有進程都成為“結束”狀態。

(7) 在所設計的程序中應有顯示或打印語句，能顯示或打印每次被選中進程的進程名以及運行一次后進程隊列的變化及各進程的參數。

本學期學習了操作系統，實驗課共有三個大實驗，共有五個題目：時間片輪轉法、高響應比優先、首次適應算法、位示圖法、文件管理。每部分都會附上實驗指導書和代碼。每個實驗都有點問題，請大家指教。

還有就是要提醒一下找到這里的學弟學妹，火哥可是知道我寫代碼的風格的，這些代碼他也都看過，如果要用在實驗作業上，請你們三思。

如果你們原封不動的復制粘貼，那就太令我失望了，師大的學風要上來啊。