我正在做一个练习,似乎卡在了如何数学地解决问题上,而不是语法上。这个想法很简单,当数字相对较小时,程序应该给定一个基数和幂,然后计算结果的数字之和。让我们用一个例子来解释我想做什么。
给定
现在,这是一个简单的例子,如果我移动到一个非常巨大的数字,比如2^1000,这几乎不可能直接投入任何我尝试过的东西中,因为结果太大并被截断。答案必须精确。
我认为也许有一种数学方法可以以不同的方式解决这个问题,将其分解成更小的块,但实际上我想不出任何其他关系,除了:
值得一提的是,我正在使用C++(也尝试了lua),也许我可以使用一个库,但这个数字将有302位数字,并且我应该编写我的程序来处理1000的指数。我真的认为我在这里缺少一些数学技巧。
编辑部分解决方案已找到
我今天花了一点时间用lua尝试解决这个问题,今晚我会用C++尝试一下,看看是否有不同的结果。我可以找到错误的来源,但我已经找到了适用于大多数情况的解决方案。只是对于2^1000和一些具有非常大数字的指数而言不适用。
我利用了模幂运算。lua代码如下:
问题在于结果本身。
你可以想象一下,输出模运算的每一个结果就像是:
当检测到前导0时,我在那里加了一个print(0),否则打印c的值。你可以看到,每个第一位数字都会被加起来以得出正确的求和结果。每行都应该包含上一行加上新数字的内容,就像基本的标题增长一样。
但是,我现在无法解决的问题是当我将其扩展到一个较大的数字时,比如我要找的解决方案。 2^1000..
结果:(健康的行,在最后)
例如,最后一行相当于将列表中的前几个数字反向排列:
给定
基数2和幂8
,因此2^8 = 256
,然后程序应该计算答案的数字之和,所以2+5+6=13
,这就是整个目的,找到一个基数的幂结果的数字之和。现在,这是一个简单的例子,如果我移动到一个非常巨大的数字,比如2^1000,这几乎不可能直接投入任何我尝试过的东西中,因为结果太大并被截断。答案必须精确。
我认为也许有一种数学方法可以以不同的方式解决这个问题,将其分解成更小的块,但实际上我想不出任何其他关系,除了:
2^1000 = 2^500*2^500
1000 log(2) = log(ans)
无论哪种方式,都无法让我得到足够的结果数字来开始求和。值得一提的是,我正在使用C++(也尝试了lua),也许我可以使用一个库,但这个数字将有302位数字,并且我应该编写我的程序来处理1000的指数。我真的认为我在这里缺少一些数学技巧。
编辑部分解决方案已找到
我今天花了一点时间用lua尝试解决这个问题,今晚我会用C++尝试一下,看看是否有不同的结果。我可以找到错误的来源,但我已经找到了适用于大多数情况的解决方案。只是对于2^1000和一些具有非常大数字的指数而言不适用。
我利用了模幂运算。lua代码如下:
-- Function purpose: Calculate modular exponent (see wiki in comment
from MooseBoys)
--
-- @param b: base
-- @param e: exponent
-- @param m: modulation
-- @result c: result
--
-- example: 2^15 = 32768
-- ModPow(2,15,10) = 8
-- ModPow(2,15,100) = 68
--
local ModPow = function(b,e,m)
local c = 1
for i = 1, e do
c = c*b%m
end
return c
end
-- Function purpose: Check uniqueness of result from last one.
-- ModPow will not return leading 0, so in the case 2^20 = 1048576
-- Sum result would equal 35 because:
-- ModPow(2,20,10^5) = 48576
-- ModPow(2,20,10^6) = 48576
--
-- Also there is an issue with rounding I am working on. Current Problem
-- Sometimes, result is 6.xxxxxxxxxx2e+294
-- and with leading 0 result is 6.xxxxxxxxxx3e+294
-- So the result does not catch there was a leading 0 since s1 and s2
-- are not equal
-- However, this fix is giving me problems (assuming mod exponent always
-- grows by an order of magnitude.. 10^(n+1) each cycle), I assumed
-- just checking exponent value is good enough
-- Now I get some strange results as outlined blow
--
-- @param s1: Current result from ModPow (as string)
-- @param s2: Last result of ModPow (as string)
-- @result bool based on whether or not this number is valid to add to the sum
local CheckUnique = function(s1,s2)
if s1:find('e') and s2:find('e') then --fix rounding?
if(s1:sub(s1:find('e'),s1:len())==s2:sub(s2:find('e'),s2:len())) then print(0) return false end
elseif (s1 == s2) then print(0) return false --fix leading 0
end
print(s1) --test
return true
end
--self explanitory
local base = 2
local exp = 1000
local mod = 10
--Counters and value holders
local sum = 0
local lval = 0
local val,valS = 1,'1'
local cycle = 1
--Know when to stop
local endval = base^exp
print(endval)
while val ~= endval do
val = ModPow(base,exp,mod^cycle)
valS = tostring(val)
if(CheckUnique(valS,lval)) then --is unique
sum = sum + tonumber(valS:sub(1,1)) --sum leading digit
end
lval = valS
cycle = cycle+1
end
print(sum)
问题在于结果本身。
你可以想象一下,输出模运算的每一个结果就像是:
Value: 1048576
6
76
576
8576
48576
0
1048576
sum: 31
当检测到前导0时,我在那里加了一个print(0),否则打印c的值。你可以看到,每个第一位数字都会被加起来以得出正确的求和结果。每行都应该包含上一行加上新数字的内容,就像基本的标题增长一样。
但是,我现在无法解决的问题是当我将其扩展到一个较大的数字时,比如我要找的解决方案。 2^1000..
结果:(健康的行,在最后)
2.6725480652012e+288
6.2672548065201e+289
8.6267366100831e+290
1.8626730674387e+291
7.186267401715e+292
0
6.0718626734093e+294
8.6071862673409e+295
0
5.0860718626736e+297
1.5086071862673e+298
7.1508607186267e+299
例如,最后一行相当于将列表中的前几个数字反向排列:
7.1508607186267e+299
7 15086071862
我很激动地发现答案是错误的。我仔细查看了这些行,并找到了这些有问题的部分:9.18229858679e+069
7.5447775000848e+070
8.8906306939456e+069
4.1746958410049e+072
5.0621122825342e+073
4.1602034907325e+074
1.9248790609684e+075 -- no such order 454879 but have 924879?
....
8.3104764719996e+086
3.8310476472e+087
4.6735451839797e+088
8.0281504870817e+089
3.0808317990698e+090
9.0430240225156e+091 --no such order 938438...?
看起来这种情况发生在几个领域,而且只在指数大于200左右的情况下发生。我检查了100次,没有问题。但我注意到在200左右的指数中存在错误。
2.9937827928353e+018
0
2.0299378279284e+020
2.2029937827928e+021
7.8493010541604e+022
5.0206666406882e+023
0
3.384239167984e+025
有人对问题有新的提示吗?(抱歉,我的lua解释器可能不同,不确定lua普遍情况下如何...我只是在使用用于游戏脚本的IDE)
好的,接近了。我的C ++程序处理得更好,这是它的代码。仍然得到错误的答案,但至少我得到了相同数量的数字。现在我似乎无法弄清楚出了什么问题。问题是,这个练习是在一个网站上进行的,我不知道正确的答案,只知道我的程序对于2^1000给我错误的答案。它通过我给它的其他测试用例(我可以手动执行并检查答案达到2^20)。
#include <iostream>
#include <cmath>
double ModPow(int,int,long double);
int main() {
int base = 2;
int power = 1000;
long double mod = 10;
long double val = 0;
int i = 0;
int sum = 0;
double ans = pow(base,power);
std::cout << ans << std::endl;
while(ans != val) {
val = ModPow(base,power,mod);
std::cout<< val << " ";
sum += int(floor(val/(mod/10)));
mod = mod * 10;
i += 1;
if(i%5 == 0) std::cout << std::endl;
}
std::cout << std::endl << sum << std::endl;
std::cout << i << std::endl;
std::cin.ignore();
return 0;
}
double ModPow(int b, int e, long double m) {
double c = 1;
for(int i = 1; i <= e; i++) {
c = fmod(c*b,m);
}
return c;
}
在这里,我看到在循环过程中存在奇怪的行为。逻辑上,每添加一个数字,指数应该每次增加一。但是我在 e+22 的位置看到了异常行为,然后它又回落到了 e+21,不确定原因。以下是我的程序完整结果(我已将双精度转换为长双精度,并添加了文件写入,但结果与上述代码相同)
6 76 376 9376 69376
69376 8.06938e+006 6.80694e+007 6.68069e+008 5.66807e+009
5.66807e+009 2.05668e+011 7.20567e+012 3.72057e+013 8.37206e+014
6.83721e+015 8.68372e+016 3.86837e+017 4.38684e+018 2.43868e+019
6.24387e+020 2.62439e+021 8.81371e+022 7.17853e+021 6.67056e+024
5.66706e+025 2.56671e+026 6.11305e+027 1.49872e+026 7.84562e+029
8.79213e+030 5.26226e+031 2.66375e+032 7.26638e+033 4.84075e+034
3.21959e+035 6.35788e+036 6.73897e+037 6.73897e+037 6.73897e+037
2.62589e+038 2.98945e+041 2.98945e+041 6.02989e+043 9.17698e+044
7.16921e+045 7.05229e+046 6.70523e+047 6.5113e+048 4.65113e+049
8.52121e+050 3.85212e+051 7.38521e+052 4.19563e+053 5.91881e+054
4.39205e+055 3.9345e+056 9.04097e+057 9.04097e+057 3.68596e+059
1.49612e+060 7.7534e+061 7.39705e+061 4.22204e+063 6.98596e+063
6.92886e+065 4.69289e+066 8.22986e+067 1.82299e+068 9.1823e+069
7.54478e+070 1.14456e+071 4.11446e+072 3.62523e+073 9.90302e+074
1.92488e+075 4.59175e+076 5.88549e+077 1.35968e+078 6.13597e+079
6.6136e+080 4.66136e+081 7.48063e+082 6.12132e+083 8.8392e+084
7.86463e+085 6.94822e+086 6.32933e+087 5.62433e+088 6.56243e+089
2.3548e+090 5.60251e+090 7.14338e+091 9.90736e+093 6.14551e+094
5.791e+095 2.5791e+096 5.12015e+097 1.81734e+098 3.08347e+099
4.30835e+100 4.43083e+101 9.44308e+102 8.62251e+103 4.79117e+104
4.47912e+105 4.70365e+106 6.26271e+107 9.63625e+108 1.34535e+109
2.5938e+110 4.77635e+110 7.92388e+112 2.33449e+113 9.38763e+114
1.74483e+115 4.23631e+116 3.8324e+117 3.10928e+118 8.8341e+119
9.80234e+120 5.28235e+121 4.52823e+122 8.69571e+123 7.59308e+124
6.61087e+123 8.34403e+126 8.26135e+127 3.82614e+128 6.83699e+128
5.48343e+130 7.05731e+131 2.02676e+132 1.20268e+133 3.72264e+134
4.37226e+135 5.43723e+136 1.68563e+137 9.63719e+138 3.70399e+139
1.84462e+140 6.61036e+141 4.66104e+142 3.85213e+143 2.38521e+144
7.39926e+145 4.95209e+146 2.70772e+147 1.27077e+148 9.49987e+149
6.39539e+150 9.72139e+151 5.89019e+152 7.15679e+153 7.15679e+153
3.38172e+154 5.84268e+156 9.72579e+157 4.87575e+158 5.6501e+159
1.85286e+160 4.18529e+161 4.60739e+162 7.12977e+163 5.71298e+164
8.86201e+165 7.8862e+166 5.82415e+167 4.61194e+168 8.46119e+169
7.95321e+170 9.01956e+171 7.90196e+172 1.40488e+173 2.38969e+174
9.12607e+175 8.5208e+176 2.61635e+177 7.26163e+178 1.87538e+179
6.18754e+180 6.6906e+181 2.05665e+182 3.79061e+183 4.37906e+184
4.43791e+185 9.87813e+186 1.98781e+187 7.03446e+188 1.57091e+189
5.7816e+190 7.57816e+191 2.1734e+191 3.5815e+193 9.77689e+194
8.97769e+195 1.08115e+196 5.10812e+197 4.6079e+198 4.46079e+199
5.44608e+200 3.69583e+201 3.36958e+202 1.94715e+203 9.19309e+204
1.7556e+205 9.45675e+206 5.94568e+207 6.45002e+208 9.11561e+209
1.17058e+210 8.60292e+211 7.86029e+212 2.48236e+213 1.2582e+214
6.04576e+215 9.60458e+216 4.34447e+217 5.43445e+218 8.42133e+219
9.84213e+220 1.8562e+221 8.38891e+221 1.08389e+223 7.01599e+223
1.07016e+225 3.10702e+226 4.3107e+227 1.50548e+228 1.06711e+229
8.65791e+230 9.86579e+231 8.18076e+232 2.68057e+232 1.85488e+234
1.85488e+234 2.26339e+236 4.66336e+237 6.27494e+238 5.24964e+239
3.52496e+240 2.99353e+240 9.96218e+242 8.99622e+243 4.9693e+243
1.33007e+245 3.78439e+246 1.99925e+247 8.51404e+248 8.47445e+249
2.95141e+250 7.13201e+251 1.7132e+252 9.76862e+253 9.36726e+254
3.92421e+255 6.39242e+256 8.42555e+256 4.87969e+258 4.09894e+259
2.17963e+260 1.61217e+261 8.27277e+261 4.08273e+263 4.53756e+264
9.67271e+265 9.67271e+265 9.19793e+267 1.91979e+268 2.52109e+267
5.12996e+270 6.60659e+271 9.64583e+272 6.96458e+273 3.07557e+274
7.59723e+275 4.30703e+276 6.07449e+277 2.87595e+278 5.82907e+279
4.59589e+279 2.07609e+281 6.20761e+282 9.17199e+283 5.9172e+284
5.9172e+284 7.05917e+286 6.70229e+287 2.67023e+288 6.26707e+289
8.62671e+290 1.86267e+291 7.18627e+292 7.18627e+292 6.07186e+294
8.60719e+295 8.60719e+295 5.08607e+297 1.50861e+298 7.15086e+299
7.15086e+299 1.07151e+301