r.amiri
سه شنبه 05 آذر 1392, 14:10 عصر
سلام دوستان گرامی
در قطعه کدی که ضمیمه کردم از روش های زیر استفاده شده :
String Manipulation ، Iteration ، Simple Search ، Brute Force
به جز Brute Force سایر روش ها رو نمیدونم ، شاید معادل دقیقشون رو متوجه نمیشم . در مورد ساختار روش های بالا امکانش هست توضیح بدین ؟ یا لینکی برای مطالعه در اختیارم قرار دهید ؟
const int MOD = 1000000009;
struct CharacterBoard2
{
// Finds x raised to the y-th exponent modulo MOD
int modPow(int x, int y)
{
long long res = 1, a = x;
while (y > 0) {
if (y & 1) {
res = (res * a) % MOD;
}
a = (a * a) % MOD;
y >>= 1;
}
return (int)res;
}
int countGenerators(vector <string> fragment, int W, int i0, int j0)
{
int r = fragment.size(), c = fragment[0].size();
int res = 0;
// For each length w:
for (int w = 1; w <= W; w++) {
map<int, char > val;
bool good = true;
// For each (i,j), find the character that should be in
// S[ ( (i0 + i)*W + (j0 + j) ) % w ], if we already knew
// this character, verify that they are equal.
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
int p = ((i0 + i)*W + (j0 + j)) % w;
if (val.count(p)) {
good = good && (val[p] == fragment[i][j]);
} else {
val[p] = fragment[i][j];
}
}
}
if (good) {
// Partial result is equal to 26 raised to the x-th power:
int x = w - val.size();
res = ( res + modPow(26, x)) % MOD;
}
}
return res;
}
};
در قطعه کدی که ضمیمه کردم از روش های زیر استفاده شده :
String Manipulation ، Iteration ، Simple Search ، Brute Force
به جز Brute Force سایر روش ها رو نمیدونم ، شاید معادل دقیقشون رو متوجه نمیشم . در مورد ساختار روش های بالا امکانش هست توضیح بدین ؟ یا لینکی برای مطالعه در اختیارم قرار دهید ؟
const int MOD = 1000000009;
struct CharacterBoard2
{
// Finds x raised to the y-th exponent modulo MOD
int modPow(int x, int y)
{
long long res = 1, a = x;
while (y > 0) {
if (y & 1) {
res = (res * a) % MOD;
}
a = (a * a) % MOD;
y >>= 1;
}
return (int)res;
}
int countGenerators(vector <string> fragment, int W, int i0, int j0)
{
int r = fragment.size(), c = fragment[0].size();
int res = 0;
// For each length w:
for (int w = 1; w <= W; w++) {
map<int, char > val;
bool good = true;
// For each (i,j), find the character that should be in
// S[ ( (i0 + i)*W + (j0 + j) ) % w ], if we already knew
// this character, verify that they are equal.
for (int i=0; i<r; i++) {
for (int j=0; j<c; j++) {
int p = ((i0 + i)*W + (j0 + j)) % w;
if (val.count(p)) {
good = good && (val[p] == fragment[i][j]);
} else {
val[p] = fragment[i][j];
}
}
}
if (good) {
// Partial result is equal to 26 raised to the x-th power:
int x = w - val.size();
res = ( res + modPow(26, x)) % MOD;
}
}
return res;
}
};