Talk:Two identical strings: Difference between revisions
→FreeBASIC black magic: -reply
(asked for clarification about structure of the binary literals) |
(→FreeBASIC black magic: -reply) |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 33:
The two "halves" ''are still'' identical, just reversed.--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 10:55, 3 April 2021 (UTC)
Here is an example program to count the different ways:
<lang csharp>using System; using static System.Console; using System.Collections.Generic;
class Program {
static void fun(bool anylead, bool palin, bool verbose = false) {
var res = new List<int>();
string s = "01", t;
for (int a = 0; a < 2; a++)
for (int b = 0; b < 2; b++)
for (int c = 0; c < 2; c++)
for (int d = 0; d < 2; d++)
for (int e = 0; e < 2; e++) {
t = "" + s[a] + s[b] + s[c] + s[d] + s[e];
for (int i = 0; i < 5; i++) {
int x = Convert.ToInt32("" + t + t, 2);
if (t[0] == '1' || anylead) if (!res.Contains(x) && x < 1000) { if (verbose) { Write("{0} ", "" + t + t); Write("({0}) ", x); } res.Add(x); }
if (palin) {
string tt = t; for (int j = t.Length - 1; j >= 0; j--) tt += t[j];
x = Convert.ToInt32(tt, 2); if (!res.Contains(x) && x < 1000) { if (verbose) {Write("{0} ", tt); Write("({0}) ", x); } res.Add(x); }
}
t = t.Substring(1);
}
}
if (verbose) WriteLine();
Write(". {0,20}, {1,5} palindromes: ", anylead ? "any leading digit" : "only starts with '1'", palin ? "allow" : "no");
WriteLine(res.Count); res.Sort(); if (verbose) WriteLine(string.Join(" ", res));
}
static void Main(string[] args) {
fun(true, true);
fun(!true, true);
fun(true, !true);
fun(!true, !true);
}
}</lang>
{{out}}
<pre>. any leading digit, allow palindromes: 91
. only starts with '1', allow palindromes: 76
. any leading digit, no palindromes: 57
. only starts with '1', no palindromes: 30</pre>--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 11:41, 3 April 2021 (UTC)
== FreeBASIC black magic ==
The [http://rosettacode.org/wiki/Two_identical_strings#FreeBASIC FreeBASIC solution] to this task is super neat! Any chance for an explanation as to how/why it works? --[[User:Chunes|Chunes]] ([[User talk:Chunes|talk]]) 12:48, 3 April 2021 (UTC)
:log n/log 2 is the number of bits - 1 representing n in binary. The formula produces n shifted left by this number + 1, then adds n.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 15:24, 3 April 2021 (UTC)
:Chunes: Nigel Galloway's explanation is correct. (Thanks, Nigel.) To help me understand it, I've added an alternate FreeBASIC version that works without utilizing <code>log()</code>. The added variable <code>p</code> (which represents <code>2^int(log(n)/log(2)</code>) 'ratchets' up the left shift amount (the <code>int(log(n)/log(2))</code> in <code>2^int(log(n)/log(2))</code>) by double, so the <code>2*n</code> in <code>k=2*n*2^int(log(n)/log(2))</code> can just be <code>n</code>, resulting in <code>k = n*p</code>.--[[User:Enter your username|Enter your username]] ([[User talk:Enter your username|talk]]) 18:33, 4 April 2021 (UTC)
:These explanations are correct. To see how it works, suppose I want to duplicate 1001 (9 in decimal). First I multiply by two enough times that I end up with 10010000, then add the 1001 again. So I need to figure out the number of spare digits I need, which is (1+floor(log_2(9)). So I take my original number n, multiply by 2^(1+floor(log_2(n)), and add n. [[User:Thebigh|Thebigh]] ([[User talk:Thebigh|talk]]) 16:03, 5 April 2021 (UTC)
| |||