Cs50 pset1 学分

Question

两周前，我对编码还很陌生，为我编写程序就像变魔术一样。几天来，我一直在绞尽脑汁寻找解决这个问题的最有效方法。最后我决定开始编写并使用更小的更简单的程序来分别解决这个问题的各个方面；我找到了我的代码中发布的解决方案。我的程序按预期工作，但我觉得我没有使用最有效的路线。

我的问题是：您可以给我一些提示和技巧来使这个程序更有效率，即编写时间或代码行数。此外，我将不胜感激任何关于如何提高效率的建议，而不仅仅是练习，即您推荐的任何书籍或流程。我已经将我的这个版本的代码提交到 cs50 系统进行评分，所以我不是要你为我做我的 HW 我只是想知道什么策略或不同的思维方式可以达到相同的结果。

提前感谢您抽出时间指导我

代码如下：

#include <stdio.h>
#include <cs50.h>
#include <math.h>

int main(void)
{
    long cc;

    do
    {
        cc = get_long("number: ");

    } while (cc < 0);

    int checksum = 0;

    {
        // 2nd digit ** henceforth all digit placement from right to left //
        checksum += (((cc / 10) % 10) * 2) / 10;
        checksum += (((cc / 10) % 10) * 2) % 10;
    }
    {
        // 4th digit //
        checksum += (((cc / 1000) % 10) * 2) / 10;
        checksum += (((cc / 1000) % 10) * 2) % 10;
    }
    {
        // 6th digit  //
        checksum += (((cc / 100000) % 10) * 2) / 10;
        checksum += (((cc / 100000) % 10) * 2) % 10;
    }
    {
        // 8th digit //
        checksum += (((cc / 10000000) % 10) * 2) / 10;
        checksum += (((cc / 10000000) % 10) * 2) % 10;
    }
    {
        // 10th digit //
        checksum += (((cc / 1000000000) % 10) * 2) / 10;
        checksum += (((cc / 1000000000) % 10) * 2) % 10;
    }
    {
        // 12th digit //
        checksum += (((cc / 100000000000) % 10) * 2) / 10;
        checksum += (((cc / 100000000000) % 10) * 2) % 10;
    }
    {
        // 14th digit //
        checksum += (((cc / 10000000000000) % 10) * 2) / 10;
        checksum += (((cc / 10000000000000) % 10) * 2) % 10;
    }
    {
        // 16th digit //
        checksum += (((cc / 1000000000000000) % 10) * 2) / 10;
        checksum += (((cc / 1000000000000000) % 10) * 2) % 10;
    }
    {
        //  1st digit //
        checksum += cc % 10;
    }
    {
        // 3rd digit //
        checksum += (cc / 100) % 10;
    }
    {
        // 5th digit //
        checksum += (cc / 10000) % 10;
    }
    {
        // 7th digit //
        checksum += (cc / 1000000) % 10;
    }
    {
        // 9th digit //
        checksum += (cc / 100000000) % 10;
    }
    {
        // 11th digit //
        checksum += (cc / 10000000000) % 10;
    }
    {
        // 13th digit //
        checksum += (cc / 1000000000000) % 10;
    }
    {
        // 15th digit //
        checksum += (cc / 100000000000000) % 10;
    }

    if (checksum % 10 == 0 && (cc / 1000000000000000) % 10 == 5
            && (cc / 100000000000000) % 10 >= 1
            && (cc / 100000000000000) % 10 <= 5)
    {
        printf("MASTERCARD\n");
    }
    else if (checksum % 10 == 0 && (cc / 1000000000000) % 10 == 4)
    {
        printf("VISA\n");
    }
    else if (checksum % 10 == 0 && (cc / 1000000000000000) % 10 == 4)
    {
        printf("VISA\n");
    }
    else if (checksum % 10 == 0 && (cc / 100000000000000) % 10 == 3
            && (cc / 10000000000000) % 10 == 4)
    {
        printf("AMEX\n");
    }
    else if (checksum % 10 == 0 && (cc / 100000000000000) % 10 == 3
            && (cc / 10000000000000) % 10 == 7)
    {
        printf("AMEX\n");
    }
    else
    {
        printf("INVALID\n");
    }

    return 0;
}

Answer 1

你的算法有点难读。有很多重复和很多大数字，其中有很多 0。因此，我建议采用不同的方法。您可以循环查看每个数字。而且，您还可以一步完成整个校验和计算。

我将向您展示如何做并解释其背后的算法。

顺便说一句。选择正确的算法永远是成功的关键。

所以，首先我们需要考虑如何从数字中提取数字。这可以通过重复以下步骤在循环中完成：

执行模 10 除法得到一个数字
做整数除以 10
重复

让我们看例子1234。

第 1 步将得到 4 -- (1234 % 10 = 4)
第 2 步会将原始数字转换为 123 -- (1234 / 10 = 123)
第 1 步将得到 3 -- (123 % 10 = 3)
第2步会将前面的数字转换成12 -- (123 / 10 = 12)
第 1 步将得到 2 -- (12 % 10 = 2)
第 2 步会将前面的数字转换为 1 -- (12 / 10 = 1)
第 1 步将得到 1 -- (1 % 10 = 1)
第2步会将前面的数字转换成0 -- (1 / 10 = 0)

然后循环停止。此外，我们还可以观察到，当除法结果为 0 时，循环停止。此外，我们还可以看到，循环执行的次数等于数字中的位数。但这在某种程度上是显而易见的。

好的，那么让我们看看到目前为止我们学到了什么

while (creditCardNumber > 0) {

    unsigned int digit = creditCardNumber % 10;
    creditCardNumber /= 10;

    ++countOfDigits;
}

这将获取所有数字并计算它们。

很好。让我们进入下一步。

为了以后的验证和比较目的，我们需要获取数字的最高有效位（第一位）和第二位（第二位）。

为此，我们定义了 2 个变量来保存数字。我们只需将当前评估的数字（并在每次循环执行中覆盖它）分配给 "mostSignificantDigit"。在循环结束时，我们将把它放在我们想要的变量中。

对于 "secondMostSignificantDigit"，我们将简单地复制 "mostSignificantDigit" 的 "old" 或 "previous" 值，然后再将新值分配给 "mostSignificantDigit"。有了它，我们将始终拥有这两个值。

循环现在看起来像这样：

while (creditCardNumber > 0) {

    const unsigned int digit = creditCardNumber % 10;

    secondMostSignificantDigit = mostSignificantDigit;
    mostSignificantDigit = digit;

    creditCardNumber /= 10;

    ++countOfDigits;
}

好的，现在我们来到可能更复杂的部分。校验和。计算方法是。

从最低位（最后一位）开始
不乘数字，相当于乘以1，加到校验和
转到下一位。乘以2，如果结果大于10，则再次取个位数，将两位加到校验和
重复

所以，秘诀是分析给定 here 的某种神秘规范。如果我们从最后一个数字开始，我们不乘它，下一个数字将被乘，下一个不是等等等等。

到"not multiply"等同于乘以1。这意味着：在循环中我们需要与1或2交替相乘。

如何在循环中获取交替数字？该算法相当简单。如果您需要交替数，比方说，x,y,x,y,x,y,x...，然后，构建 x 和 y 的总和并执行减法 "value = sum - value"。例子：我们需要交替取值 1 和 2。总和为 3。要获得下一个值，我们从总和中减去当前值。

初始值 = 1
总和 = 3
当前值=初始值=1
下一个值 = 3 - 1 = 2。当前值 = 2
下一个值 = 3 - 2 = 1。当前值 = 1
下一个值 = 3 - 1 = 2。当前值 = 2
下一个值 = 3 - 2 = 1。当前值 = 1
下一个值 = 3 - 1 = 2。当前值 = 2
下一个值 = 3 - 2 = 1。当前值 = 1
。 . .

很好，现在我们明白了，如何制作交替值。

接下来，如果我们将一个数字乘以 2，那么最大结果可能是一个 2 位的值。我们得到模数和整数除以 10 的个位数。

而且，现在重要的是，如果我们相乘或不相乘并不重要，因为如果我们不相乘，那么高位数字将永远为 0。这不会影响总和。

综上所述，我们始终可以进行乘法并将结果拆分为 2 位数字（其中许多的高位数字为 0）。

结果将是：

checkSum += (digit * multiplier) % 10 + (digit * multiplier) / 10;
multiplier = 3 - multiplier;

一个非常简单的公式。

接下来，如果我们了解 C 或 C++，我们也知道与 2 的乘法可以通过向左移位非常有效地完成。此外，"no-multiplication" 可以通过移位 0 来完成。这比乘法非常高效且更快。

x * 1 等同于 x << 0
x * 2 等同于 x << 1

对于最终结果，我们将使用此机制，在 0 和 1 之间交替乘数并进行移位。

这将为我们提供非常有效的校验和计算。

在程序结束时，我们将使用所有收集到的值并将它们与规范进行比较。

这将导致：

int main() {

    // Get the credit card number. Unfortunately I do not know CS50. I use the C++ standard iostream lib.
    // Please replace the following 4 lines with your CS50 equivalent
    unsigned long long creditCardNumber;
    std::cout << "Enter credit card number: ";
    std::cin >> creditCardNumber;
    std::cout << "\n\n";

    // We need to count the number of digits for validation
    unsigned int countOfDigits = 0;

    // Here we will calculate the checksum
    unsigned int checkSum = 0;

    // We need to multiply digits with 1 or with 2
    unsigned int multiplier = 0;

    // For validation purposes we need the most significant 2 digits
    unsigned int mostSignificantDigit = 0;
    unsigned int secondMostSignificantDigit = 0;

    // Now we get all digits from the credit card number in a loop
    while (creditCardNumber > 0) {

        // Get the least significant digits (for 1234 it will be 4)
        const unsigned int digit = creditCardNumber % 10;

        // Now we have one digit more. In the end we will have the number of all digits
        ++countOfDigits;

        // Simply remember the most significant digits
        secondMostSignificantDigit = mostSignificantDigit;
        mostSignificantDigit = digit;

        // Calculate the checksum
        checkSum += (digit << multiplier) % 10 + (digit << multiplier) / 10;

        // Multiplier for next loop 
        multiplier = 1 - multiplier;

        creditCardNumber /= 10;
    }
    // Get the least significant digit of the checksum
    checkSum %= 10;

    // Validate all calculated values and show the result
    if ((0 == checkSum) &&                  // Checksum must be correct AND
        (15 == countOfDigits) &&            // Count of digits must be correct AND
        ((3 == mostSignificantDigit) &&     // Most significant digits must be correct 
        ((4 == secondMostSignificantDigit) || (7 == secondMostSignificantDigit)))) {
        std::cout << "AMEX\n";
    }
    else if ((0 == checkSum) &&             // Checksum must be correct AND
        (16 == countOfDigits) &&            // Count of digits must be correct AND
        ((5 == mostSignificantDigit) &&     // Most significant digits must be correct
        ((secondMostSignificantDigit > 0) && (secondMostSignificantDigit < 6)))) {
        std::cout << "MASTERCARD\n";
    }
    else if ((0 == checkSum) &&             // Checksum must be correct AND
        ((16 == countOfDigits) || (13 == countOfDigits)) && // Count of digits must be correct AND
        ((4 == mostSignificantDigit))) {    // Most significant digit must be correct
        std::cout << "VISA\n";
    }
    else {
        std::cout << "INVALID\n";
    }
    return 0;
}

我们从这个例子中学到的是整数除法和模除法以及 identity element 用于二元运算的巧妙用法。

如有问题，请提问

为了完整起见，我将向您展示一个基于 std::string 并使用现代 C++ 元素和算法的 C++ 解决方案。

例如，整个校验和计算将用一条语句完成。整个程序不包含任何循环。

#include <iostream>
#include <string>
#include <regex>
#include <numeric>

int main() {

    // ---------------------------------------------------------------------------------------------------
    // Get user input
    // Inform user, what to do. Enter a credit card number. We are a little tolerant with the input format
    std::cout << "\nPlease enter a credit card number:\t";

    // Get the number, in any format from the user
    std::string creditCardNumber{};
    std::getline(std::cin, creditCardNumber);

    // Remove the noise, meaning, all non digits from the credit card number
    creditCardNumber = std::regex_replace(creditCardNumber, std::regex(R"(\D)"), "");

    // ---------------------------------------------------------------------------------------------------
    // Calculate checksum
    unsigned int checksum = std::accumulate(creditCardNumber.rbegin(), creditCardNumber.rend(), 0U,
        [multiplier = 1U](const unsigned int sum, const char digit) mutable -> unsigned int {
        multiplier = 1 - multiplier; unsigned int value = digit - '0';
        return sum + ((value << multiplier) % 10) + ((value << multiplier) / 10); });

    // We are only interested in the lowest digit
    checksum %= 10;

    // ---------------------------------------------------------------------------------------------------
    // Validation and output
    if ((0 == checksum) &&                      // Checksum must be correct AND
        (15 == creditCardNumber.length()) &&    // Count of digits must be correct AND
        (('3' == creditCardNumber[0]) &&        // Most significant digits must be correct 
        (('4' == creditCardNumber[1]) || ('7' == creditCardNumber[1])))) {
        std::cout << "AMEX\n";
    }
    else if ((0 == checksum) &&                 // Checksum must be correct AND
        (16 == creditCardNumber.length()) &&    // Count of digits must be correct AND
        (('5' == creditCardNumber[0]) &&        // Most significant digits must be correct
        ((creditCardNumber[1] > '0') && (creditCardNumber[1] < '6')))) {
        std::cout << "MASTERCARD\n";
    }
    else if ((0 == checksum) &&                 // Checksum must be correct AND
        ((16 == creditCardNumber.length()) || (13 == creditCardNumber.length())) && // Count of digits must be correct AND
        (('4' == creditCardNumber[0]))) {       // Most significant digit must be correct
        std::cout << "VISA\n";
    }
    else {
        std::cout << "INVALID\n";
    }
    return 0;

Cs50 pset1 学分

Cs50 pset1 Credit

c

cs50