(急)要在一小時內解決~各位喜愛C語言的人幫忙想想八

[passiontcfsh 10]

請大家有空幫幫忙分擔兩題問題

要在一個小時內解決

一、[Dynamic Programing]某國家一共發行了1元、3元、4元三種不同面額的鈔票。

現在我們手上有n元, 請問(a)要如何把n元兌換成1元、3元、4元這些鈔票，使得所用鈔票的量為最少。

(b)兌換後的鈔票各為幾張

輸入: n （0 < n < 1000 ）;

輸出:

(a)最少的張數。(b) 1元、3元、4元三種不同面額鈔票的張數

(假設有三種不同面額的鈔票 1元、3元、4元，若要兌換10元的鈔票，最少鈔票的量為 ? 張。一般若用10/4=2，再用餘數去2/1=2 ，則會用4張; 可是若3元2張，再1張4元就可以了，只要3張)

輸入範例:

10

39

輸出範例:

(a)3 (b)0 2 1

(a)10 (b)0 1 9

二、請設計一程式，可以找出所有符合下列特性的運算式A×B=C，(1) 其中A，B， C均為整數；且A是兩位數，B是三位數，C為五位數，(2)所有A、B、和C的組成十進位數字(合起來共有十個十進位數字)全部皆相異。例如，27594=16038和78345=26910等皆符合以上特性。本題沒有輸入，請直接顯示出所有符合特性的運算式，並計算共有幾種不同的運算式。輸入：(無)

輸出：列出所有符合特性的運算式，並計算共有幾種不同的運算式。

參考答案

27 X 594 = 16038

36 X 495 = 17820

39 X 402 = 15678

45 X 396 = 17820

46 X 715 = 32890

52 X 367 = 19084

54 X 297 = 16038

63 X 927 = 58401

78 X 345 = 26910

共9種運算式

[JS1037 10]

你這篇是現在在考試還是交作業阿...

[9-AE 10]

我猜是電腦課

[su_horng 10]

原來JS會逛這個版XD

[JS1037 10]

原來JS會逛這個版XD

我可是四處探尋你的下落說服你去同學會呢xd

[伊達政宗 11]

這是第一題

雖然過了一小時了

第二題有限時嗎???

假如沒有，就暴力解囉~

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{

    int money = 0;
    scanf("%d",&money);

    int count[money+1];
    int coin[3] = {1,3,4};
    int get[money+1];

    for(int i=0;i<=money;i++){
        count[i] = 0;
        get[i] = -1;
    }

    for(int i=0;i<3;i++){
        count[coin[i]] = 1;
        get[coin[i]] = i;
    }

    for(int i=0;i<=money;i++){
        if(count[i]>0) continue;
        count[i] = count[i-coin[0]]+1;

        for(int j=0;j<3;j++)
            if(i-coin[j]>=0&&count[i-coin[j]]+1<count[i]){
                count[i] = count[i-coin[j]]+1;
                get[i] = j;
            }
    }

    printf("%d\n",count[money]);

    int HowtoGet[3] = {0,0,0};

    for(int i=money;i>=0;i-=coin[get[i]])
        HowtoGet[get[i]]++;

    for(int i=0;i<3;i++)
        printf("%d ",HowtoGet[i]);
    printf("\n");


    system("PAUSE");
    return EXIT_SUCCESS;
}

此內容已被編輯, June 15, 2011 ,由 伊達政宗

[j100002ben 10]

第二題有限時應該也不用解很久...

我用Python 1.2秒就出來了

C的解法應該也是暴力解...

解答其實很簡單，就只是單純的陣列+for迴圈

不過左邊兩位數和三位數只有三位數的中間那個數字有可能是0

因為個位數如果是0右邊乘出來的結果就會有0，但是不能重複

左點最高位數不能是0應該也不用解釋了XDD

以下是Python

num_used = []
def f(x): return num_used.count(x) == 0
def stringToInt(x): return int(x)
#Do not need to test 0 due to two-digits number
for i in range(1,10):
	num_used.append(i)
	#Do not need to test 0 due to last digit cannot be 0
	for j in filter(f, range(1,10)):
		num_used.append(j)
		#Do not need to test 0 due to three-digits number
		for x in filter(f, range(1,10)):
			num_used.append(x)
			for y in filter(f, range(0,10)):
				num_used.append(y)
				for z in filter(f, range(1,10)):
					num_used.append(z)
					mul_num = (i*10 + j) * (x*100 + y*10 + z)
					if filter(f, range(0,10)) == map(stringToInt, sorted(list(str(mul_num)))):
						print str(i) + str(j), 'X', str(x) + str(y) + str(z), '=', mul_num
					num_used.remove(z)
				num_used.remove(y)
			num_used.remove(x)
		num_used.remove(j)
	num_used.remove(i)

補一個整理過用遞迴的版本

current_digits = []
def f(x): return current_digits.count(x) == 0
def getNextDigit(index):
	if index == 5:
		mul_num = int(''.join(map(str, current_digits[:2]))) * int(''.join(map(str, current_digits[2:])))
		if map(str, filter(f, range(0,10))) == sorted(list(str(mul_num))):
			print ''.join(map(str, current_digits[:2])), 'X', ''.join(map(str, current_digits[2:])), '=', mul_num
		return 
	for digit in filter(f, range(0,10) if index == 3 else range(1,10)):
		current_digits.append(digit)
		getNextDigit(index+1)
		current_digits.pop()
if __name__ == '__main__':
	getNextDigit(0)

此內容已被編輯, June 16, 2011 ,由 j100002ben