C#字符无法正确计数(算法)

huangapple go评论77阅读模式
英文:

C# characters cannot be counted correctly (algorithm)

问题

I've translated the provided text as requested. Here's the translated content:

今天我尝试解决一个ACSL算法问题时,遇到了以下问题:

输入:将有三个整数,分别表示要找到的值的数量,要在2到9之间(包括2和9)使用的基数,以及在给定基数中不超过16位数字的起始值。
输出:对于每组3个输入值,输出一个表示输入基数中最大数字在生成的数字序列中出现的次数的十进制数。

示例:如果n=15,b=8,s=2,则生成的数字是2、3、4、5、6、7、10、11、12、13、14、15、16、17、20。基数8中可能的最大数字是7,它出现了2次。

我按照说明进行操作,以下是最小可重现代码:

static void Main(string[] args)
{
    Console.WriteLine(TheFunc(25, 5, 324));
    // 应该输出24,但它输出10
}
public static int TheFunc(int n, int b, int s)
{
    List<string> num = new List<string>();
    string temp = "";
    int SumCount = 0;
    for (int i = 0; i < n; i++)
    {
        num.Add(ChangeBaseEX(s + i, b));
    }

    foreach (var single in num)
    {
        temp += single;
    }

    SumCount = temp.Length - temp.Replace((b - 1).ToString(), "").Length;

    return SumCount;
}

public static string ChangeBaseEX(int num, int changeto)
{
    string TheNumber = "";
    int RestNumber = 0;
    while (num > 0)
    {
        RestNumber = num % changeto;
        TheNumber = RestNumber.ToString() + TheNumber;
        num = num / changeto; //num/=changeto
    }
    return TheNumber;
}

当我输入15, 8, 2时,可以正确显示结果为2。然而,当我输入25, 5, 324时,它输出10,这是错误的(正确的输出应该是24)。

我尝试过以下:

1:
我尝试确定我的ChangeBaseEX函数是否正确:

Console.WriteLine(ChangeBaseEX(20, 8));
Console.WriteLine(ChangeBaseEX(4000, 6));
Console.WriteLine(ChangeBaseEX(22, 2));
//24
//30304
//10110

根据在线进制转换工具,我的进制转换是正确的。

2:
我尝试打印每个值,以确定我的计数是否有问题,但似乎一切都正确:

//Console.WriteLine(s + i);
//Console.WriteLine(ChangeBaseEX(s + i, b));
//Console.WriteLine("=======");

3:
我尝试以许多不同的方式编写相同的代码。例如,我尝试将SumCount = temp.Length - temp.Replace((b - 1).ToString(), "").Length;更改为许多其他方式,如single.Length - single.Replace((b - 1).ToString(), "").Length;

4:
我尝试使用单步调试,但我没有发现任何问题。

我已经调试了每个可疑的步骤,但没有发现问题。在这种情况下,我想知道我哪一步操作出错,以导致计数不正确。

【注意】我已将代码部分保持不变,只翻译了文本内容。

英文:

When I am trying to solve an ACSL algorithm question today, I encountered the following question:

> INPUT: There will be three integers representing the number of values to be found, the base to be used between 2 and 9 inclusive, and the starting value in the base given that will be no more than 16 digits.<br>
OUTPUT: For each set of 3 input values, output a base 10 number representing the number of
times the largest digit in the inputted base occurs in the sequence of numbers generated.

> EXAMPLE: If n=15, b=8, and s=2, the numbers generated are 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20. The largest possible digit in base 8 is 7 which occurs 2 times.

I followed the instruction and this is the Minimum Reproducible Code:

    static void Main(string[] args)
    {
        Console.WriteLine(TheFunc(25,5,324));
        // it should be 24, but it outputs 10
    }
    public static int TheFunc(int n, int b, int s)
    {
        List&lt;string&gt; num = new List&lt;string&gt;();
        string temp = &quot;&quot;;
        int SumCount = 0;
        for (int i = 0; i &lt; n; i++)
        {
            num.Add(ChangeBaseEX(s + i, b));
        }

        foreach (var single in num)
        {
            temp += single;
        }

        SumCount = temp.Length - temp.Replace((b - 1).ToString(), &quot;&quot;).Length;

        return SumCount;

    }
    public static string ChangeBaseEX(int num, int changeto)
    {
        string TheNumber = &quot;&quot;;
        int RestNumber = 0;
        while (num &gt; 0)
        {
            RestNumber = num % changeto;
            TheNumber = RestNumber.ToString() + TheNumber;
            num = num / changeto; //num/=changeto
        }
        return TheNumber;
    }

When I type 15, 8, 2, it can show the result correctly, which is 2. However, when I type 25, 5, 324, it outputs 10, which is incorrect(the correct output should be 24).
<h1>what I tried:</h1>

1:
I tried to determine if my ChangeBaseEX function is correct:

        Console.WriteLine(ChangeBaseEX(20, 8));
        Console.WriteLine(ChangeBaseEX(4000, 6));
        Console.WriteLine(ChangeBaseEX(22, 2));
        //24
        //30304
        //10110

According to Online base conversion tool, my base conversion is correct.

2:
I tried to print every value to determine if there are anything wrong with my counting, but it seemed that it is correct:

            //Console.WriteLine(s + i);
            //Console.WriteLine(ChangeBaseEX(s + i, b));
            //Console.WriteLine(&quot;=======&quot;);

3:
I tried to write the same code in many different ways. For example, I tried to change SumCount = temp.Length - temp.Replace((b - 1).ToString(), &quot;&quot;).Length; into many other ways such as single.Length - single.Replace((b - 1).ToString(), &quot;&quot;).Length;.

4:
I tried to use single step debugging, but I found nothing wrong.

<h1>What I want:</h1>
I debugged every suspicious step and I found nothing wrong. In that case, I want to know which step I get wrong to let it count incorrectly.

<br>
<br>

<!--(just in case, I found this post on meta.stackoverflow.com, and this question is proper)-->

答案1

得分: 2

你错过了第三个数字是用指定的基数表示的这一事实。所以在基数为5的情况下,324实际上是十进制值89

你需要将该值作为字符串传递,并将其从基数N转换为整数值,然后将其用作你数字序列的起始点。

例如:

static int CountMaxDigitsInSequence(int count, int baseNumber, string startValue)
{
	if (baseNumber < 2 || baseNumber > 9)
		throw new ArgumentOutOfRangeException($"Invalid base number: {baseNumber}");
	if (startValue.Length > 16)
		throw new ArgumentException($"Start value too long: \"{startValue}\"");
	
	// 将Base-N字符串转换为起始值
	int start = FromBaseN(startValue, baseNumber);
	
	// 获取要搜索的数字
	char searchDigit = (char)('0' + baseNumber - 1);
	// 或者:(baseNumber - 1).ToString()[0];
	
	// 计数器
	int result = 0;
	
	// 循环遍历所需的值列表
	for (int i = 0, value = start; i < count; i++, value++)
	{
		// 将当前值转换为Base-N中的字符串
		string text = ToBaseN(value, baseNumber);
		// 计算我们要搜索的数字的出现次数
		foreach (var c in text)
		{
			if (c == searchDigit)
				result++;
		}
	}
	
	return result;
}

// 将Base-N中的数字转换为整数
// 其中:
// 2 <= baseNumber <= 9
static int FromBaseN(string value, int baseNumber)
{
	if (baseNumber < 2 || baseNumber > 9)
		throw new ArgumentOutOfRangeException($"Invalid base number: {baseNumber}");
	int result = 0;
	foreach (char c in value)
	{
		int digit = (int)(c - '0');
		if (digit < 0 || digit >= baseNumber)
			throw new ArgumentException($"Invalid digit '{c}' in value \"{value}\".");
		result = result * baseNumber + digit;
	}
	return result;
}

// 将整数转换为特定基数的字符串。
// 其中:
// value > 0
// 2 <= baseNumber <= 9
static string ToBaseN(int value, int baseNumber)
{
	if (baseNumber < 2 || baseNumber > 9)
		throw new ArgumentOutOfRangeException($"Invalid base number: {baseNumber}");
	if (value < 0)
		throw new ArgumentException($"Invalid value: {value}");
	string result = string.Empty;
	while (value > 0)
	{
		int digit = value % baseNumber;
		value /= baseNumber;
		// 这有点不太规范,但它有效。
		result = digit.ToString() + result;
	}
	return result;
}

还有一个用Span<char>减少分配次数的简化的ToBaseN()实现,只是为了好玩:

static string ToBaseN(int value, int baseNumber)
{
	Span<char> buffer = stackalloc char[17];
	int index = 1;
	while (value > 0)
	{
		buffer[^(index++)] = (char)('0' + value % baseNumber);
		value /= baseNumber;
	}
	return new string(buffer[^(index)..]);
}
英文:

You missed the fact that the third number is expressed in the indicated base. So 324 in base 5 is actually the decimal value 89.

You'll need to pass the value in as a string, convert it from Base-N to an integer value, then use that as the starting point of your number sequence.

For instance:

static int CountMaxDigitsInSequence(int count, int baseNumber, string startValue)
{
if (baseNumber &lt; 2 || baseNumber &gt; 9)
throw new ArgumentOutOfRangeException($&quot;Invalid base number: {baseNumber}&quot;);
if (startValue.Length &gt; 16)
throw new ArgumentException($&quot;Start value too long: \&quot;{startValue}\&quot;&quot;);
// Convert the Base-N string to a starting value
int start = FromBaseN(startValue, baseNumber);
// Get digit to search for
char searchDigit = (char)(&#39;0&#39; + baseNumber - 1);
// Or: (baseNumber - 1).ToString()[0];
// Counter
int result = 0;
// loop through the desired value list 
for (int i = 0, value = start; i &lt; count; i++, value++)
{
// Convert current value to string in Base-N
string text = ToBaseN(value, baseNumber);
// Count instances of our search digit
foreach (var c in text)
{
if (c == searchDigit)
result++;
}
}
return result;
}
// Convert a number in Base-N to an integer
// Where:
//	2 &lt;= baseNumber &lt;= 9
static int FromBaseN(string value, int baseNumber)
{
if (baseNumber &lt; 2 || baseNumber &gt; 9)
throw new ArgumentOutOfRangeException($&quot;Invalid base number: {baseNumber}&quot;);
int result = 0;
foreach (char c in value)
{
int digit = (int)(c - &#39;0&#39;);
if (digit &lt; 0 || digit &gt;= baseNumber)
throw new ArgumentException($&quot;Invalid digit &#39;{c}&#39; in value \&quot;{value}\&quot;.&quot;);
result = result * baseNumber + digit;
}
return result;
}
// Convert an integer to a string in a paticular base.
// Where:
//	value &gt; 0
//	2 &lt;= baseNumber &lt;= 9
static string ToBaseN(int value, int baseNumber)
{
if (baseNumber &lt; 2 || baseNumber &gt; 9)
throw new ArgumentOutOfRangeException($&quot;Invalid base number: {baseNumber}&quot;);
if (value &lt; 0)
throw new ArgumentException($&quot;Invalid value: {value}&quot;);
string result = string.Empty;
while (value &gt; 0)
{
int digit = value % baseNumber;
value /= baseNumber;
// This is a little dirty, but it works.
result = digit.ToString() + result;
}
return result;
}

And just for fun, here's a stripped-down ToBaseN() implementation using Span&lt;char&gt; to reduce the number of allocations.

static string ToBaseN(int value, int baseNumber)
{
Span&lt;char&gt; buffer = stackalloc char[17];
int index = 1;
while (value &gt; 0)
{
buffer[^(index++)] = (char)(&#39;0&#39; + value % baseNumber);
value /= baseNumber;
}
return new string(buffer[^(index)..]);
}

huangapple
  • 本文由 发表于 2023年7月18日 13:10:52
  • 转载请务必保留本文链接:https://go.coder-hub.com/76709668.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定