求可处理20000以内金额的ATM最少纸币找零TypeScript实现

Hey there! I see you're new to JavaScript/TypeScript and need help building a flexible ATM cash change program that uses the minimum number of banknotes. Let's work through this step by step.

First, let's recap your requirements clearly: #

• Language: TypeScript
• Input constraints: Withdrawal amount must be a multiple of 100, between 100 and 20000 inclusive; account balance must be ≥ withdrawal amount
• Output: An array representing the banknote denominations (with counts) for the withdrawal, plus the updated account balance
• Rule: Use the minimum number of banknotes (the greedy algorithm works perfectly here since your denominations fit the greedy property)

Solution Approach #

The greedy algorithm is ideal for this scenario—we start with the largest denomination and take as many as possible, then move to the next smaller denomination until we've covered the full withdrawal amount. For your use case, we'll use denominations in descending order: [2000, 1000, 500, 100] (this matches your sample example).

TypeScript Implementation #

Here's a complete, tested implementation with input validation and clear output:

// Define valid denominations in descending order (critical for greedy algorithm)
const DENOMINATIONS = [2000, 1000, 500, 100];

interface CashChangeResult {
  updatedBalance: number;
  banknotes: Array<{ denomination: number; count: number }>;
}

function calculateCashChange(balance: number, withdrawalAmount: number): CashChangeResult | string {
  // Step 1: Validate all input constraints
  if (withdrawalAmount < 100) {
    return "Error: Withdrawal amount must be at least 100";
  }
  if (withdrawalAmount > 20000) {
    return "Error: Withdrawal amount cannot exceed 20000";
  }
  if (withdrawalAmount % 100 !== 0) {
    return "Error: Withdrawal amount must be a multiple of 100";
  }
  if (balance < withdrawalAmount) {
    return "Error: Insufficient account balance";
  }

  // Step 2: Calculate updated account balance
  const updatedBalance = balance - withdrawalAmount;

  // Step 3: Compute minimum banknotes using greedy logic
  let remainingAmount = withdrawalAmount;
  const banknotes: Array<{ denomination: number; count: number }> = [];

  for (const denom of DENOMINATIONS) {
    if (remainingAmount >= denom) {
      const count = Math.floor(remainingAmount / denom);
      banknotes.push({ denomination: denom, count });
      remainingAmount -= count * denom;
    }
    // Exit early once we've covered the full withdrawal amount
    if (remainingAmount === 0) break;
  }

  return { updatedBalance, banknotes };
}

// Example usage (matches your sample scenario)
const sampleBalance = 3000;
const sampleWithdrawal = 2600;
const result = calculateCashChange(sampleBalance, sampleWithdrawal);

if (typeof result !== "string") {
  console.log(`Updated Balance: ${result.updatedBalance}`);
  console.log("Banknotes:");
  result.banknotes.forEach(note => {
    console.log(`${note.denomination} * ${note.count}`);
  });
} else {
  console.log(result);
}

How This Works #

1. Input Validation: We first check all your constraints to catch invalid inputs early (like non-100 multiples, amounts outside the allowed range, or insufficient balance).
2. Greedy Calculation: By iterating from largest to smallest denomination, we ensure we use the fewest notes possible. For your sample (2600 withdrawal):
   • Take 1 x 2000 (remaining: 600)
   • Take 1 x 500 (remaining: 100)
   • Take 1 x 100 (remaining: 0)
3. Structured Output: The result returns both the updated balance and an array of objects clearly showing each denomination and how many of each are needed.

Customization Tips #

• If you need to support different denominations, just update the DENOMINATIONS array (keep it in descending order for the greedy algorithm to work correctly).
• If you prefer the output as a flat array of denominations (e.g., [2000, 500, 100] instead of counts), modify the banknotes collection step to push each denomination count times into an array.

内容的提问来源于stack exchange，提问作者Abhishek Gautam