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的大數(shù)。
此舉確實流氓了一點，不過確實過了，鄙人的第一題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》里關(guān)于 大數(shù)的簡單介紹，講的算比較清晰的了：
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èi)容

利用高級語言，設(shè)計一個采用二級或二級以上的多級文件目錄管理系統(tǒng)，實現(xiàn)對文件的基本操作，如：文件的建立、打開、關(guān)閉、復(fù)制、撤銷、檢索等。

二、實驗?zāi)康?/span>

用高級語言編寫和調(diào)試一個簡單的文件系統(tǒng)，模擬文件管理的工作過程。從而對各種文件操作命令的實質(zhì)內(nèi)容和執(zhí)行過程有比較深入的了解。

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

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

三、實驗環(huán)境

1．PC微機(jī)。

2．Windows 操作系統(tǒng)。

3．C/C++/VB開發(fā)集成環(huán)境。

四、實驗題目

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

算法設(shè)計思想：

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

（2）       文件保護(hù)簡單使用了三位保護(hù)碼：允許讀寫執(zhí)行、對應(yīng)位為 1，對應(yīng)位為0，則表示不允許讀寫、執(zhí)行。

（3）       程序中使用的主要設(shè)計結(jié)構(gòu)如下：

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

一、實驗內(nèi)容

利用高級語言模擬進(jìn)程的時間片輪轉(zhuǎn)調(diào)度算法，響應(yīng)比高者優(yōu)先調(diào)度算法。

二、實驗?zāi)康?/span>

在采用多道程序設(shè)計的系統(tǒng)中，往往有若干個進(jìn)程同時處于就緒狀態(tài)。當(dāng)就緒進(jìn)程個數(shù)大于處理器數(shù)時，就必須依照某種策略來決定哪些進(jìn)程優(yōu)先占用處理器。本實驗?zāi)M在單處理器情況下的處理器調(diào)度，幫助學(xué)生加深了解處理器調(diào)度的工作。

三、實驗環(huán)境

1．PC微機(jī)。

2．Windows 操作系統(tǒng)。

3．C/C++/VB開發(fā)集成環(huán)境。

四、實驗題目

本實驗有兩個小題。

第一題：設(shè)計一個按時間片輪轉(zhuǎn)法實現(xiàn)處理器調(diào)度的程序。

算法設(shè)計思想：

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

其中，進(jìn)程名——作為進(jìn)程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程名分別為Q₁，Q₂，Q₃，Q₄，Q₅。

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

要求運行時間——假設(shè)進(jìn)程需要運行的單位時間數(shù)。

已運行時間——假設(shè)進(jìn)程已經(jīng)運行的單位時間數(shù)，初始值為“0”。

狀態(tài)——有兩種狀態(tài)，“就緒”和“結(jié)束”，初始狀態(tài)都為“就緒”，用“R”表示。當(dāng)一個進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。

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

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

標(biāo)志單元

         K₂   

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

已運行時間+1

來模擬進(jìn)程的一次運行，表示進(jìn)程已經(jīng)運行過一個單位的時間。

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

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

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

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

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

第二題：設(shè)計一個按響應(yīng)比高者優(yōu)先調(diào)度算法實現(xiàn)進(jìn)程調(diào)度的程序。

算法設(shè)計思想：

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

其中，進(jìn)程名——作為進(jìn)程的標(biāo)識，假設(shè)五個進(jìn)程的進(jìn)程名分別為P₁，P₂，P₃，P₄，P₅。

指針——按優(yōu)先數(shù)的大小把五個進(jìn)程連成隊列，用指針指出下一個進(jìn)程的進(jìn)程控制塊的首地址，最后一個進(jìn)程中的指針為“0”。

要求運行時間——假設(shè)進(jìn)程需要運行的單位時間數(shù)。

等待時間——自最近一次調(diào)度運行至今等待的時間數(shù)，當(dāng)進(jìn)程被調(diào)度時等待時間清零。

響應(yīng)比——進(jìn)程調(diào)度程序運行前計算每個進(jìn)程的響應(yīng)比，調(diào)度時總是選取響應(yīng)比大的進(jìn)程先執(zhí)行，每次執(zhí)行一個固定的時間片。

狀態(tài)——可假設(shè)有兩種狀態(tài)，“就緒”狀態(tài)和“結(jié)束”狀態(tài)。五個進(jìn)程的初始狀態(tài)都為“就緒”，用“R”表示，當(dāng)一個進(jìn)程運行結(jié)束后，它的狀態(tài)為“結(jié)束”，用“E”表示。

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

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

  隊首標(biāo)志

         K₂   

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

提醒注意的是：在實際的系統(tǒng)中，當(dāng)一個進(jìn)程被選中運行時，必須恢復(fù)進(jìn)程的現(xiàn)場，讓它占有處理器運行，直到出現(xiàn)等待事件或運行結(jié)束。在這里省去了這些工作。

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

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

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

本學(xué)期學(xué)習(xí)了操作系統(tǒng)，實驗課共有三個大實驗，共有五個題目：時間片輪轉(zhuǎn)法、高響應(yīng)比優(yōu)先、首次適應(yīng)算法、位示圖法、文件管理。每部分都會附上實驗指導(dǎo)書和代碼。每個實驗都有點問題，請大家指教。

還有就是要提醒一下找到這里的學(xué)弟學(xué)妹，火哥可是知道我寫代碼的風(fēng)格的，這些代碼他也都看過，如果要用在實驗作業(yè)上，請你們?nèi)肌?/p>

如果你們原封不動的復(fù)制粘貼，那就太令我失望了，師大的學(xué)風(fēng)要上來啊。