我正在嘗試找到一種演算法來列印 n 的所有除數（包括 1 和 n），但它只能是遞回的，只有 1 個輸入，根本沒有回圈。我試圖玩弄素數，也許正在尋找一種模式，但我似乎找不到沒有 afor或 a的方法while。所以函式的宣告必須void divisors( int n )是遞回的。我不想要一個完整的代碼，因為它是一個作業，我更多的是尋找一個提示，或者一個我可能會丟失的觀點
uj5u.com熱心網友回復：
據我了解：
- 函式的宣告必須是
void divisors( int n ) - 它需要是遞回的
- 沒有
斗篷回圈
一種解決方案是使用間接遞回。這允許實作輔助函式以在額外引數中維護狀態，但輔助函式可以呼叫divisors(). 在這樣做時，它被遞回呼叫。
因此，例如，您可以使用帶符號的值來指示divisors()應該將負值列印為除數。
void divisors (int n) { if (n > 0) { printf("divisors of %d:", n); divisors2(n, 1); } else if (n < 0) printf(" %d", -n); else printf("\n"); }
并且遞回divisors2()將divisors()使用負引數呼叫以列印找到的除數。
void divisors2 (int n, int p) { if (p > n) { divisors(0); return; } if (!(n % p)) divisors(-p); divisors2(n, p); }
uj5u.com熱心網友回復：
正如@CraigEstey 所記錄的，經典的遞回方法需要第二個引數。由于原型是固定的，您需要另一種方法來跟蹤當前除數。你可以：
- 使用全域變數
- 使用區域靜態變數。
- 使用除數的部分引數，大大減少了初始呼叫的值范圍。
這不是很優雅，但似乎沒有違反規則。
這是一個帶有執行緒區域static變數的示例：
void divisors(int n) { static _Thread_local int p = 0; if (p == 0) { printf("divisors of %d:", n); } if (p > n) { printf("\n"); p = 0; return; } if (n % p == 0) { printf(" %d", p); } divisors(n); }
如果您愿意更多地濫用規則，這里有一個更簡單的符合標準的規則：
- 符合原型
void divisors(int n) - 沒有
for或while回圈 - 遞回的使用
void divisors(int n) { int p = 1; if (n <= 0) return; printf("divisors of %d:", n); next: if (n % p == 0) printf(" %d", p); if (p < n) goto next; printf("\n"); divisors(0); // dummy recursive call }
uj5u.com熱心網友回復：
更新
假設您只能使用 int 引數，如下所示：
void divisors(int n)
作弊并使用引數的高位，n作為存盤當前除數的一種方式傳入。有一些合理的假設：2 的補碼，8 位位元組，并且 int 至少為 32 位寬。但這在當今幾乎是普遍的。
對于和with的任何一對因子n，則最多為。保存一個數字的平方根需要一半的位數。所以我們的 1/3 位用于除數，另外 2/3 位用于我們試圖分解的值。xyx<yxsqrt(n)
如果在 32 位 int 上妥協，則范圍限制為 21 位，或者0 <= n <= 2097151
void divisors(int n)
{
unsigned int un = (unsigned int) n;
size_t width = sizeof(n) * 8;
// we can use up to 1/3 of our bits to hold the divisor
size_t valueprecision = (width * 2)/3;
size_t divprecision = width-valueprecision;
unsigned int divisor = un >> valueprecision;
unsigned int mask = (unsigned int)(-1);
mask = mask >> divprecision;
unsigned int value = un & mask;
if (divisor == 0)
{
divisor = 1;
}
if (value % divisor == 0)
{
printf("%d\n", divisor);
if (divisor != (value/divisor))
{
printf("%d\n", value / divisor);
}
}
divisor ;
// the stopping point is when divisor > sqrt(value), or divisor*divsor > value
if ((divisor * divisor) > value)
{
return;
}
un = (divisor << valueprecision) | value;
divisors(un);
}
呼叫divisors(2097151)列印：
1
2097151
7
299593
49
42799
127
16513
337
6223
889
2359
uj5u.com熱心網友回復：
這不能用一個引數來完成。
我意識到了這一點（和其他人一樣）
Eric 在評論中提出了理由/證據，所以我將在這里總結它們：
也許吧，但 OP 并沒有說問題規范規定了該簽名。相反，他們說“所以函式的宣告必須是……”，這表明簽名是他們自己從單輸入要求得出的結論。如果是這樣，那是不正確的；有一個輸入的要求承認其他簽名的可能性。——埃里克·波斯特皮希爾
假設例程傳遞了一個數字 n，并且應該列印 n 的所有除數。鑒于例程必須是遞回的，它可能會以某個因子 n 呼叫自身，例如 f。該遞回呼叫將列印 f 的所有因子。然后通過 n 的呼叫必須列印 n 的所有因素，但這些因素不是 f 的因素，我將其稱為額外因素。也許它可以用自己的代碼來做這件事，或者它可以用遞回呼叫來做。然而，一個問題是這些因素的數量是不同的。例如，如果 n 為 14，f 為 7，則有兩個額外的因子，2 和 14……——Eric Postpischil
… 但是，如果 n 為 30，f 為 15，則有 4 個額外因子，2、6、10 和 30。可以有任意多個額外因子。這意味著例程不能進行固定數量的列印；它必須使用一些回圈。但是禁止使用回圈，而不是遞回。此外，無法通過對例程的遞回呼叫來列印額外的因子，因為 1 是任何正整數的因子，因此任何遞回呼叫都必須列印 1；它不能限制為 2、6、10 和 30。因此，如果可以實作無回圈遞回解決方案，則無法通過僅傳遞要因式分解的數字來完成。——埃里克·波斯特皮希爾
從以上：
所以，雖然我們需要：
void divisors(int n)
這并不排除輔助功能（例如）
void divrec(int n,int f)
f當前要測驗的除數/因子在哪里。
印刷1和n作為因素必須是特殊情況。
但是，在那之后，divrec可以遞回地呼叫自己，從divisors呼叫開始：divrec(n,2)。如果精心設計，編譯器優化器將執行“尾遞回”，因此我們不會炸毀堆疊。
實際功能非常簡單，如果不實際顯示它就很難“暗示”它，但是：
- 如果
f > n，停止/回傳。 - 如果能被整除，則列印
n并被整除。ffnf - 否則，增加
f1。 - 遞回呼叫
divrec更新的n和f值。
IMO，生成的 C 代碼比這里的偽代碼描述更容易理解。
這是示例代碼。注釋如下：
#include <stdio.h>
typedef long long num;
#define DIVME(_expr) \
do { \
printf("EXPR: " #_expr "\n"); \
divisors((num) _expr); \
} while (0)
void
prt(num f)
{
printf(" %lld",f);
}
void
divrec(num n,num f)
// n -- remaining number
// f -- current factor to try
{
// at this point, we've "looped" f all the way from 2 to n
if (f > n)
return;
// got a factor:
// (1) print it
// (2) reduce the number down
// (e.g.) number divisible by 2 -- next try is (n / 2,2)
if ((n % f) == 0) {
prt(f);
n /= f;
}
// number is _not_ divisible by current factor -- increase the factor by 1
// (e.g.) number is _not_ divisible by 2 -- next try is (n,3)
else
f = 1;
// ensure "tail recursion" so we do _not_ blow up the stack
// (with optimization)
// NOTE: on my system, this generates an internal loop in the asm insts
// generated
divrec(n,f);
}
void
divisors(num n)
{
// special case for n/1:
prt(1);
prt(n);
printf("\n");
divrec(n,2);
printf("\n");
}
int
main(void)
{
DIVME(2 * 3 * 5 * 7 * 11 * 13 * 17 * 23 * 29 * 31 * 3 * 7 * 13 * 13);
return 0;
}
這是程式輸出：
EXPR: 2 * 3 * 5 * 7 * 11 * 13 * 17 * 23 * 29 * 31 * 3 * 7 * 13 * 13
1 37462588393230
2 3 3 5 7 7 11 13 13 13 17 23 29 31
更新：
橫向思維呢？– chqrlie
哈哈哈......好吧，如果你堅持...... :-)
我曾考慮過其他答案使用的[一些]技巧，但決定反對它們，因為使用分段數字、全域變數或“間接”遞回是[有點]“作弊”。我認為我的方法是最不“作弊”的，但現在，它有類似的“氣味”:-)
所以，也許是時候重新考慮和澄清問題陳述了......
從OP的第一句話：
我試圖找到一種演算法來列印 n 的所有除數（包括 1 和 n），但它只能是遞回的，只有 1 個輸入，根本沒有回圈。
IMO，這是問題陳述。
這是OP的第二句話：
我試著玩弄素數，也許正在尋找一種模式，但我似乎找不到沒有 a
for或 a 的方法while
IMO，這[只是] OP對問題的解決方案/解釋。
因此，除數有兩種定義：
- https://en.wikipedia.org/wiki/Divisor
- https://en.wikipedia.org/wiki/Division_（數學）
(1) 似乎是每個人[錯誤地:-)] 使用的東西。
但是，從 (2) 開始，對于除法，除數只是可以除以給定數字（即）的任何 [和所有] 數字：
quotient remainder = dividend / divisor
考慮到第二個定義，給定數字的除數是和（包括）之間n的任何和所有數字，而不考慮余數。1n
所以，這里是更新的代碼：
void prt(int n);
void
divisors(int n)
// n -- remaining number
{
// at this point, we've "looped" all the way from n to 1
if (n < 1)
return;
prt(n);
divisors(n - 1);
}
uj5u.com熱心網友回復：
這是我的第二次嘗試。一個更大的黑客。
由于這是“任何事情都會發生”，包括冒未定義行為的風險，我認為這是解決這個問題的公平游戲。
該解決方案在當前函式呼叫上方借用無人認領的堆疊記憶體，以將當前“除數”變數存盤在堆疊中高出約 4k 的位置。在隨后的遞回中，該記憶體不太可能被遞回占用，但在記憶體不可用的情況下不會那么高。
它確實使用了一個回圈 - 但只是在堆疊中找到除數
生產準備好了嗎？- 不！
安全且不受未定義行為的影響？- 當然不！
現代編譯器中的堆疊保護技術怎么樣？- 編譯器可能在當前堆疊指標下方的資料上插入了篡改保護，但似乎并未保護堆疊指標上方的未使用區域。
編譯器優化會打破關于堆疊的假設嗎？編譯器可以隨意使用它想要的任何優化來破壞這個解決方案。我發現了一個printf似乎可以阻止 gcc 進行尾遞回優化的 hack。
便攜式-大聲笑。當它依賴于未定義的行為時，我不能聲稱它是真正可移植的。但它適用于優化的 Visual C 、Clang 和 gcc。
看它在這里運行
void divisors(int n)
{
// scan upward in the stack by up to looking for the guard bytes that proceed the
// divisor variable we are stashing. If not found, assume 0
if (n < 0)
{
return;
}
int* stackptr = &n;
const int stashoffset = 1000;
int* ptr1 = stackptr - stashoffset;
int* ptr2 = ptr1 1;
int divisor = 0;
printf("", &n); // this thwarts gcc optimizations
// go look for where a previous recursion may have hid the divisor
for (int i = 0; i < stashoffset; i )
{
if ((*ptr1 == 0xdeadbeef) && (*ptr2 == 0xdeadbeef))
{
divisor = ptr2[1];
*ptr1 = 0;
*ptr2 = 0;
break;
}
ptr1 ;
ptr2 ;
}
divisor ;
if (n % divisor == 0)
{
printf("%d, %d\n", divisor, n / divisor);
}
if ((divisor * divisor) >= n)
{
return;
}
// stash the divisor way up there in the stack and put
// some dead beef around it to it can be discovered in the next recursion
ptr1 = stackptr - stashoffset;
ptr2 = ptr1 1;
*ptr1 = 0xdeadbeef;
*ptr2 = 0xdeadbeef;
ptr2[1] = divisor;
divisors(n); // recurse here
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/468822.html
上一篇：C寫和讀單個字符